递归算法深入解析

• 递归使用举例（求一个数的阶乘）

public class Main {

    public static void main(String[] args) {
        int total = factorial(5);
        System.out.println(total);
    }

    /**
        求阶乘
     */
    private static int factorial(int num) {
        if (num == 0 || num == 1){
            return 1;
        }
        int value = num * factorial(num - 1);
        return value;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

递归产生的条件：

1. 在函数中调用本方法，也就是自己调用自己。
2. 必须要有结束条件，因为递归不可能是无限制的，当触发某一条件时，开始结束递归。

运行阶乘方法，查看方法调用栈

点击每个调用栈，可以看到每个方法栈中运行时保存的变量信息，例如第五次方法栈中，num的值是1，方法执行结束，将1返回出去，来到第4层

第四层的调用栈num值是2，而num * 上一层的返回值也就是value 也是2,那么这一层的返回值就是 2 * 1 = 2.

第三层的num是 3 * 上一次层的返回值 2 = 6

第四层的num是4 * 上一层的返回值 6 = 24.

第五层的num是5*上一层的返回值24 = 120

此时第一层的factorial执行结束，将结果返回给main方法，factorial弹栈，main输出结果，main方法执行完成。

递归算法就是通过自己调用自己实现方法调用栈不断入栈，当进入到递归终止条件判断时开始进行弹栈，本次执行的返回值会给到下一个方法，直到所有方法都执行完成。这个过程要直到结束条件是什么。

• 方法调用栈

在方法执行的过程中，每当调用另一个方法时，方法调用栈都会记录到当前方法执行到哪一行。

最开始执行的肯定是先入栈，main方法先入栈，此时main:9，表示执行到第9行时调用了其他方法，等待其他方法执行完后，继续从第9行开始执行。factorial是递归调用，执行到了21行，而最后一次递归调用执行到了18行又调用了print方法。通过方法调用栈保存的每个方法在上一个方法弹栈后应从哪一行继续执行我们可以很清除看到方法之间的调用关系。而每个方法都是一块独立的栈空间，共享了堆空间，引用类型数据都存在了堆空间里，这样在递归返回引用类型数据的时候也不会丢失引用。