【基础算法】递归

• 这是递归的终止条件，用于防止无限递归。当问题规模缩小到一定程度时，可以直接得到答案，不需要再进行递归调用。例如，在计算阶乘时，当  或  时，阶乘的值为 1，这就是基础情况。

• 函数在自身内部调用自己，每次调用时，问题的规模会逐渐减小。比如在计算斐波那契数列时，就是递归调用，通过不断地调用自身来计算出前两项的值，从而得到第 n 项的值。
• 

• 数学定义：
• 代码实现（以 Java 为例）：

public class Factorial {
    public static int factorial(int n) {
        if (n == 0 || n == 1) {
            return 1;
        } else {
            return n * factorial(n - 1);
        }
    }
}

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

1. 优点
   • 代码简洁：对于一些具有递归性质的问题，递归算法可以使代码非常简洁和直观，能够清晰地表达问题的求解逻辑。例如，树的遍历（先序、中序、后序遍历）使用递归算法可以很容易地实现。
   • 易于理解：对于一些复杂的问题，将其分解为相似的子问题，符合人们的思维习惯，更容易理解问题的解决方案。
2. 缺点
   • 效率问题：递归调用会产生额外的函数调用开销，包括保存函数的调用栈、参数传递等。在某些情况下，可能会导致性能下降，尤其是当递归深度很深时，可能会占用大量的栈空间，甚至导致栈溢出。例如，在计算较大的斐波那契数时，由于存在大量的重复计算，效率会比较低。
   • 空间复杂度高：由于递归调用需要保存每一层的函数调用信息，所以空间复杂度可能会比较高。在最坏的情况下，空间复杂度可能与递归深度成正比。

1. 树和图的遍历：如二叉树的先序、中序、后序遍历，图的深度优先搜索等。
2. 分治算法：例如归并排序、快速排序等排序算法都是基于分治策略，其中包含递归的思想。
3. 动态规划的递归解法：有些动态规划问题可以使用递归的方式来解决，通过记忆化搜索可以提高效率。