Java 关于递归的调用机制精细解读

什么是递归？

递归是一种解决问题的方法，定义了一个函数在内部调用自身的方法，可以实现较为简洁的代码。递归的关键是要寻找到递归的出口，也就是递归结束的条件。

递归的调用过程

递归调用过程分为两个阶段，递推阶段和回归阶段。在递推阶段，程序会执行入口参数不同但是算法过程相同的代码；在回归阶段，程序会执行返回值相同甚至参数相同但是算法过程不同的代码。下面我们通过两个示例分别来解释这两个阶段。

示例一：计算阶乘

阶乘是从 1 到指定数字的连乘积。假设我们需要计算 5 的阶乘，可以通过递归完成。

public int factorial(int n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

递推阶段

假设我们传入的参数是 5。程序首先会执行 factorial(5) 方法，然后调用 factorial(4) 方法。接着，程序会进入下一次的递归，调用 factorial(3) 方法，并依次推进到 factorial(2) 和 factorial(1) 方法。到了 factorial(1) 方法，递归结束，直接返回 1。

回归阶段

接下来程序开始回归，将 factorial(1) 的结果带回到 factorial(2) 方法中，计算 2 * factorial(1) 的值，返回 2。然后再返回到 factorial(3)，计算 3 * factorial(2) 的值，返回 6。重复这个过程直到 factorial(5) 方法的返回值被计算出来。

示例二：斐波那契数列

斐波那契数列是一个经典的递归问题，它的递推公式是 F(n) = F(n-1) + F(n-2)。

public int fibonacci(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

递推阶段

假设我们传入的参数是 5。程序首先会执行 fibonacci(5) 方法，然后调用 fibonacci(4) 方法和 fibonacci(3) 方法。随后，程序进一步递推，依次调用 fibonacci(3) 和 fibonacci(2) 方法，以及 fibonacci(2) 和 fibonacci(1) 方法。到了 fibonacci(2) 和 fibonacci(1) 方法，递归结束，直接返回 1。

回归阶段

接下来程序开始回归，将 fibonacci(2) 和 fibonacci(1) 的结果带回到 fibonacci(3) 方法中，计算 2 的值，返回。接着再将 fibonacci(3) 的结果带回到 fibonacci(4) 和 fibonacci(5) 方法中，分别计算 3 和 5 的值，直到 fibonacci(5) 方法的返回值被计算出来。

总结

递归是一种常用的算法，但是需要注意其调用过程以及递归结束的条件。还需要注意在递归方法中，需要使用合适的数据类型进行递归，避免产生不必要的错误。通过示例，我们可以更好地理解递归的调用机制，以及递推阶段和回归阶段的区别。