什么是递归（Recursion）

递归是一种在编程中常用的算法设计策略，通过函数直接或间接地调用自身来解决问题。递归的核心思想是将一个复杂的问题分解成更小的、相似的问题，直到问题变得足够简单，可以直接解决。

它在多种场景下都非常有用。以下是一些常见的使用递归的情况：

1. 树和图的遍历：
   • 二叉树、N叉树、图等结构的深度优先搜索（DFS）和广度优先搜索（BFS）通常使用递归实现。
   • 遍历文件系统或目录结构时，递归可以用来访问每个文件或目录。
2. 分治算法：
   • 递归是分治策略的核心，如归并排序、快速排序等算法，通过递归将问题分解成更小的子问题，解决后再合并结果。
3. 动态规划：
   • 某些动态规划问题，如斐波那契数列、最长公共子序列等，可以通过递归（带备忘录或动态规划表）来解决。
4. 回溯算法：
   • 解决组合问题，如八皇后问题、数独求解器、排列组合问题等，递归用于探索所有可能的解。
5. 数学计算：
   • 计算阶乘、幂运算等数学问题时，递归提供了一种简洁的实现方式。
6. 字符串和数组操作：
   • 字符串的模式匹配（如 KMP 算法），数组的子序列问题等，递归可以用来简化代码。
7. 递归数据结构：
   • 处理递归定义的数据结构，如链表、树等，递归是自然的选择。
8. 递归函数：
   • 某些函数本身就是递归定义的，如阶乘、斐波那契数列等。
9. 解析和编译技术：
   • 编译器中的语法分析器，如 LL(1)、LR(1) 分析器，通常使用递归下降分析来解析语法。
10. 人工智能和机器学习：
    • 搜索算法，如 Minimax 算法、深度优先搜索等，常用于游戏 AI 和决策树。
11. 装饰器和高阶函数：
    • 在某些编程语言中，递归可以用来实现装饰器或高阶函数，以处理函数的组合和复用。
12. 算法竞赛：
    • 在算法竞赛中，递归常用于解决复杂的算法问题，因为它可以简化问题分解的过程。

递归可以拆分为以下两个阶段：

• 递：程序不断深入地调用自身，经过设计的一系列算法将问题分解成更小的问题，并调用自身来解决这些更小的问题，直到达到终止条件后，停止调用。
• 归：达到终止条件后，程序开始从最深层的递归函数逐层返回，积累每一层的结果。

对于代码实现方面主要分为以下三部分：

• 终止条件：用于决定什么时候由递转归。如果没有该条件，程序会无限递下去，最终会导致程序栈溢出错误。
• 递归调用：对应递。这是函数调用自身的过程。在这一步，函数将问题分解成更小的问题，并调用自身来解决这些更小的问题。
• 返回结果：对应归。将当前递归层级的结果返回至上一层。

这里以C++代码为例，实现等差数列求和函数
$$
f(n) =1 + 2 + 3 + ··· + n
$$

1
2
3
4
5
6
7
8
9
10
11

int recursion(int n){
  //终止条件（必须添加）
  if(n==1){
    return 1;
  }
  //递归调用
  const int res = n + recursion(n-1);
  
  //返回结果
  return res;
}

下图展示了该递归函数的过程

从图上可以看出递归将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式。接下来将子问题继续分解为更小的子问题，直到触发终止条件时停止。

函数转化为
$$
f(n)=n+f(n-1)
$$
不断（递归地）分解下去，直至基本情况
$$
f(1)=1
$$
时终止。

调用栈

递归函数每次调用自身时，系统都会为其开启新的函数分配内存，以存储局部变量、调用地址和其他信息等。这将导致两方面的结果。

• 函数的上下文数据都存储在称为栈帧空间的内存区域中，直至函数返回后才会被释放。因此，递归通常比迭代更加耗费内存空间。
• 递归调用函数会产生额外的开销。因此递归通常比循环的时间效率更低。

尾递归

但是有趣的是，如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空间效率上与迭代相当。这种情况被称为尾递归（tail recursion）。

尾递归是一种特殊的递归形式，它允许函数在执行完递归调用之后不再进行任何操作。这意味着尾递归可以被编译器优化，以避免增加调用栈的深度，从而避免栈溢出错误，即使递归调用非常深。

以上面代码为例，具体代码如下：

1
2
3
4
5
6
7
8

/* 尾递归 */
int tailRecur(int n, int res) {
    // 终止条件
    if (n == 0)
        return res;
    // 尾递归调用
    return tailRecur(n - 1, res + n);
}

和普通递归相比，尾递归的求和执行方式是有区别的

• 普通递归：求和操作是在归的过程中执行的，每层返回后都要再执行一次求和操作。因此系统都保存每一层的函数信息，如局部变量、调用地址和其他信息等
• 尾递归：求和操作是在递的过程中执行的，归的过程只需层层返回。而尾递归递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后，无须继续执行其他操作，因此系统无须保存上一层函数的上下文。

尾递归过程如图所示

实践

相信到这里你已经对递归有了一个深刻的认识，那么接下来我们做一个例题，来加深一下递归的用法。

斐波那契数列的函数原型为：
$$
数列的前两个数字为：f(1)=0 ，f(2)=1
$$

$$
数列中的每个数字是前两个数字的和：f(n)=f(n-1)+f(n-2),n>2
$$

函数代码：

1
2
3
4
5
6
7
8
9

int Algorithm::fibonacci(int n) {
    // 终止条件 f(1) = 0, f(2) = 1
    if(n==1||n==2) {
        return 1;
    }
    int res = fibonacci(n-1)+fibonacci(n-2);
    //返回结果
    return res;
}

大家是否都做对了。如果做对了，那么你已经对递归有了更深的理解，接下来就是多刷题，下面是LeetCode中关于递归的算法题，大家去可以尝试一下，进一步巩固对递归的理解。