两个小例子轻松搞懂 java 中递归与尾递归的优化操作

下面我来详细讲解“两个小例子轻松搞懂 Java 中递归与尾递归的优化操作”的完整攻略。

什么是递归以及尾递归？

在 Java 中，递归即一个方法在执行的过程中调用了它自身。在某些情况下，递归会导致栈溢出。尾递归优化是一种特殊类型的递归，它可以将递归过程转化为迭代过程，从而防止栈溢出。

示例 1：计算斐波那契数列

首先我们来看一个计算斐波那契数列的例子：

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

以上代码是一个递归实现的斐波那契数列计算过程。

当 n 的值非常大时，递归调用次数也会非常多，最终会导致栈溢出。因此，我们需要对递归过程进行优化，使其能够处理更大的 n 值。

下面是修改后的尾递归优化版代码：

public static int fibonacciTailRecursive(int n, int a, int b) {
    if (n == 0) {
        return a;
    }
    if (n == 1) {
        return b;
    }
    return fibonacciTailRecursive(n - 1, b, a + b);
}

public static int fibonacci(int n) {
    return fibonacciTailRecursive(n, 0, 1);
}

在尾递归优化版代码中，我们使用了另一个帮助方法 fibonacciTailRecursive(). fibonacciTailRecursive() 方法中有三个参数，分别是 n、a 和 b。

a 和 b 分别对应每次递归调用时斐波那契数列中的两个数。初始值 a = 0、b = 1。

如果 n == 0，函数直接返回 a；如果 n == 1，函数直接返回 b。

函数主体部分是一个递归调用，当前递归调用是以 n - 1、b 和 a + b 作为新的入参，再次进入递归。当递归结束时，函数直接返回结果。

这样，在每次调用 fibonacciTailRecursive() 时，都可以将它的结果作为参数传递给下一个递归调用，从而杜绝栈溢出。

示例 2：计算阶乘

接下来看一个计算阶乘的示例：

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

这是一个标准的递归计算阶乘的代码。随着 n 的增大，函数的递归深度会增加，导致栈溢出的风险增大。

现在让我们来对这个函数进行尾递归优化：

public static long factorialTailRecursive(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return factorialTailRecursive(n - 1, n * acc);
}

public static long factorial(int n) {
    return factorialTailRecursive(n, 1);
}

在上述代码中，我们使用了 factorialTailRecursive() 这个帮助方法。factorialTailRecursive() 方法中有两个参数，分别是 n 和一个累加器 acc。

acc 初始值为 1。如果 n == 0，函数直接返回 acc；否则，将 n 和 acc 的积作为新的 acc 值，递归调用 factorialTailRecursive()。

这样，在每次调用 factorialTailRecursive() 时，都可以将上一次计算得到的 acc 作为参数传递给下一个递归调用，从而避免栈溢出的风险。

总结

综上，递归虽然很常见并且在有些情况下也很好用，但是在某些带有递归深度的情况下会导致栈溢出。因此，在需要递归的时候，我们需要对递归过程进行优化，以获得更好的性能和更高的可用性。

通过对斐波那契数列和阶乘的示例的分析，我们可以看到如何使用尾递归来优化递归函数。注意，在递归函数特别深的时候，尾递归可以帮助我们消除栈的限制，从而实现更高的性能和更好的可用性。