设一个未知函数f，用其自身构成的已知函数g来定义：
f(n)=g(n ,f(n-1)) n>0
f(0)=a n=0
为了定义f(n)，必须先定义f(n-1)，为了定义f(n-1)，又必须先定义f(n-2)··· ···，上述这种用自身的简单情况来定义自己的方式称为递归定义。
一个递归定义必须是有确切含义的，也就是说，必须一步比一步简单，最后是有终结的，决不能无限循环下去。在f(n)的定义中，当n为0时定义一个已知数a，是最简单的情况，称为递归边界，它本身不再使用递归的定义。
与递推一样，每一个递归定义都有其边界条件。但不同的是，递推是由边界条件出发，通过递推式求f(n)的值，从边界到求解的全过程十分清楚；而递归则是从函数自身出发来达到边界条件。在通往边界条件的递归调用过程中，系统用堆栈把每次调用的中间结果（局部变量和返回地址值）保存起来，直至求出递归边界值f(0)=a。然后返回调用函数。返回过程中，中间结果相继栈恢复，f(1) = g(1 ,a) —> f(2) = g(2, f(1)) —> ··· —>直至求出f(n) = g(n , f(n - 1))。
递归按其调用方式分：
- 直接递归 — 递归过程P直接自己调用自己；
- 间接递归 — 即P包含另一过程D，而D又调用P；
递归算法适用的一般场合为：
- 数据的定义形式按递归定义。
如裴波那契数列的定义： fn=fn-1 + fn-2; f0=1; f1=2。
对应的递归程序实现为：
public class FibonacciImpl {
public static void main(String[] args) {
final int n = 10;
for (int i = 0; i < n; i++ ){
System.out.print(fibonacci(i) + " ");
}
}
private static int fibonacci(int n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return 2;
}
return (fibonacci(n - 2) + fibonacci(n - 1));
}
}
结果为：
1 2 3 5 8 13 21 34 55 89
- 数据之间的关系（即数据结构）按递归定义。如树的遍历，图的搜索等。
- 问题解法按递归算法实现。例如回溯法等。
对于2，3，可利用堆栈结构将其转换为非递归算法。
