设一个未知函数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；

递归算法适用的一般场合为：

1. 数据的定义形式按递归定义。
   如裴波那契数列的定义： f_n=f_n-1 + f_n-2; f₀=1; f₁=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. 问题解法按递归算法实现。例如回溯法等。

对于2，3，可利用堆栈结构将其转换为非递归算法。