什么是递归？

递归是一种编程技巧，函数自己调用自己，就像俄罗斯套娃一样，一层套一层。

递归的本质

把大问题分解成相似的子问题，直到问题足够小可以直接解决。

生活中的递归例子

  • 俄罗斯套娃：打开一个大娃娃，里面有一个小娃娃，再打开又是更小的娃娃…
  • 镜子中的镜子：两面镜子相对放置，你会在镜子中看到无限多个自己的影像
  • 剥洋葱：剥掉一层皮，里面还有一层皮，直到最里面的小洋葱

递归的核心原理

递归的两个关键部分

1. 基准条件 (Base Case)：递归的终点，防止无限递归

2. 递归步骤 (Recursive Step)：将问题分解为更小的子问题

递归的执行过程

  1. 函数调用自身
  2. 每次调用时问题规模应更小
  3. 到达基准条件时停止递归
  4. 回溯返回结果

递归三要素

1. 定义明确的基准条件

必须有一个或多个不需要递归就能直接得到结果的简单情况。

2. 递归调用必须缩小问题规模

每次递归调用都向基准条件靠近一步。

3. 递归调用必须解决更小的相同问题

子问题与原问题在结构上保持一致但规模更小。

经典递归示例：阶乘计算

数学定义：n! = n × (n-1) × (n-2) × … × 1

递归定义：n! = n × (n-1)! 且 0! = 1

C语言实现

// 递归函数计算阶乘
int factorial(int n) {
  // 1. 基准条件：0!和1!都等于1
  if (n == 0 || n == 1) {
    return 1;
  }
  // 2. 递归步骤：n! = n × (n-1)!
  else {
    return n * factorial(n – 1);
  }
}

调用过程分析（以 factorial(4) 为例）

调用顺序 函数调用 返回值 解释
1 factorial(4) 4 × factorial(3) 递归调用
2 factorial(3) 3 × factorial(2) 递归调用
3 factorial(2) 2 × factorial(1) 递归调用
4 factorial(1) 1 基准条件
返回3 factorial(2) 2 × 1 = 2 计算结果
返回2 factorial(3) 3 × 2 = 6 计算结果
返回1 factorial(4) 4 × 6 = 24 最终结果

递归的优缺点

优点：

  • 代码简洁优雅 – 递归可以用少量代码表达复杂的逻辑
  • 更符合人类思维 – 对分治类问题（如树结构遍历）表达更自然
  • 简化复杂问题 – 将大问题分解为小问题，降低思考难度

缺点：

  • 内存消耗大 – 每次递归调用都会占用栈空间
  • 效率较低 – 存在重复计算（可通过记忆化优化）
  • 栈溢出风险 – 递归太深可能导致栈溢出
  • 调试困难 – 递归调用堆栈较深时调试较麻烦

温馨提示： 对于递归深度不确定的问题，优先考虑迭代循环解决方案。递归更适合问题规模随递归减小的情况。

递归与迭代的对比

特性 递归 迭代（循环）
代码简洁性 ★★★★★ ★★★☆☆
内存占用 高（使用栈空间） 低（通常只需固定空间）
性能 较低（函数调用开销） 较高
适用问题 树、图遍历，分治算法 线性处理，简单重复操作
栈溢出风险 有 无

常用递归算法示例

1. 斐波那契数列

// 递归计算斐波那契数列
int fibonacci(int n) {
  if (n <= 1) {
    return n; // 基准条件
  }
  return fibonacci(n-1) + fibonacci(n-2);
}

2. 汉诺塔问题

// 汉诺塔递归解法
void hanoi(int n, char from, char to, char aux) {
  if (n == 1) {
    printf(“Move disk 1 from %c to %c\n”, from, to);
    return;
  }
  hanoi(n-1, from, aux, to);
  printf(“Move disk %d from %c to %c\n”, n, from, to);
  hanoi(n-1, aux, to, from);
}

3. 二叉树遍历

// 递归实现二叉树中序遍历
void inorderTraversal(TreeNode* root) {
  if (root == NULL) return; // 基准条件

  inorderTraversal(root->left); // 遍历左子树
  printf(“%d “, root->val); // 访问根节点
  inorderTraversal(root->right); // 遍历右子树
}