数学中经常有这样的函数，它自己定义自己。例如：n的阶乘函数f(n)=n!，n为整数：
f(n)=1? ? ?n<=1
f(n)=nf(n-1)? ?n>1
当n小于或等于1时，f(n)的值为1，例如f(-3)=f(0)=f(1)=1。当n大于1时，f(n)是递归定义的，因为右侧也有f。但这不会导致循环完义，因为右侧f的参数小于左侧f的参数。例如，f(2)=2f(1)，因为f(1)=1，所以f(2)=2*1=2,以此类推，f(3)=3f(2)=3*2=6。
假定f(n)是直接递归的。要使函数f(n)的递归定义有一个完全的形式，需要满足如下条件：
- 有一个基础部分（base component)，它包含n的一个或多个值，对这些值，f(n)是直
接定义的（即不用递归就能求解）。为简单起见，我们假定f的定义域是非负整数，基
础部分包含0<=n<=k，其中k为作负常数。（n>=k的情形也是可能的，但很少见。） - 在递归部分（recursive component），右侧f有一个参数小于n，因此重复应用递归部分可以把右侧f的表达式转变为基础部分。
在上面公式中，基础部分是f(n)=1，n<=1；递归部分是f(n)=nf(n一l)，右侧f的参数
是n-1，比n小。重复应用递归部分将f（n一l)转变为f(n-2）,f(n-3），…，直到f(1)，而f(1)属于基础部分。例如：
f(5)=5f(4)=20f(3)=60f(2)=120f(l)
注意，递归部分的每一次应用都使我们更接近基础部分。最后应用基础部分，我们得到
f(5)=]20。从这个例子中我们看到的是f(n)=n(n-l)(n-2)…1? (n>=1)。
递归定义的另一个例子是斐波那契数列：
F0=0, F1=1, Fn=Fn-1+Fn-2 (n>1)
其中F0=1和F1=1是基础部分，Fn=Fn-1+Fn-2是递归部分。右侧的数参数比n小。要使
公式成为完全递归形式，从n>1开始反复应用递归部分，每次n的值都要减去1或2，
最终将右侧F的表达式转化为基础部分的表达式。例如，
F4 =F3+F2=F2+F1+F0=3F1+2F0=3