递归的数学函数

假定f(n)是直接递归的。要使函数f(n)的递归定义有一个完全的形式,需要满足如下条件:
有一个基础部分(base component),它包含n的一个或多个值,对这些值,f(n)是直接定义的(即不用递归就能求解)。为简单起见,我们假定f的定义域是非负整数,基础部分包含0<=n<=k,其中k为作负常数。(n>=k的情形也是可能的,但很少见。)

在递归部分(recursive component),右侧f有一个参数小于n,因此重复应用递归部分可以把右侧f的表达式转变为基础部分。