带你了解Java数据结构和算法之递归

什么是递归？

递归是一种算法或计算机程序的设计方法，在程序执行过程中直接或间接的调用自身。

递归的实现方式

递归的实现通常使用函数进行的。在函数中，我们首先检查停止条件（递归基）是否满足，如果满足，我们停止递归；否则，我们调用自身递归进行下一步计算。

递归的应用场景

递归通常在解决问题中使用。对于像树、图等复杂结构的遍历和搜索，递归很常见。

示例 1：计算阶乘

下面是一个递归计算阶乘的示例。我们使用阶乘的定义进行递归计算。

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

函数接收一个整数 n 作为参数，并返回 n! 的值。当 n 小于等于 1 时，递归基被触发，结束递归调用。在其他情况下，函数将返回 n 与 n -1 的阶乘的乘积。正如您所看到的，递归把大问题切分成小的子问题，重复解决子问题。

示例 2：斐波那契数列

下面是一个递归计算斐波那契数列的示例。

public static long fibonacci(int n) {
    if (n <= 1) {
        return n;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

函数接收一个整数 n 作为参数，并返回斐波那契数列的第 n 项。当 n 小于等于 1 时，递归基被触发，结束递归调用。在其他情况下，函数将返回前面两个斐波那契数列的项之和。这种递归计算一般只用于小数值的 n，如果 n 很大，递归会变得非常缓慢，这是因为存在大量的重复计算。

总结

递归是一种非常有用的程序设计方法，它可以使代码更加简洁和优雅，但如果使用不当，可能会影响程序的性能。在实现递归算法时，需要小心处理递归的基本情况，并避免重复计算。