本页目录

8-7 递归

发布时间:

一、 什么是递归？​

递归是指函数在执行过程中直接或间接调用自身的编程技巧。

  • 递归把一个大问题分解为相似的子问题
  • 每个子问题与原问题具有相同的解决思路
  • 直到子问题简单到可以直接求解
void f() {
  ...
  f();  // 函数调用自己
}

二、 递归三要素​

1. 基准条件 ​

递归的终止条件，防止无限循环

if (n == 0) return;

2. 递归条件 ​

函数调用自身的条件

else return f(n-1);

3. 向基准靠近 ​

每次递归都应使问题规模减小

n -> n-1 -> n-2 ...

三、 递归执行过程：以阶乘为例​

int fact(int n) {
  if (n <= 1)
    return 1;
  return n * fact(n-1);
}

fact(4) 的执行过程：

js 
fact(4) = 4 * fact(3)
fact(3) = 3 * fact(2)
fact(2) = 2 * fact(1)
fact(1) = 1  ← 基准条件
回代：2 * 1 = 2 → 3 * 2 = 6 → 24

四、 递归调用栈​

每次递归调用都会在内存中创建一个新的栈帧，保存：

  • 函数的参数值
  • 函数的局部变量
  • 返回地址（调用位置）

当到达基准条件时，栈帧开始逐层弹出，将结果返回给上一层调用。

栈空间是有限的，递归太深可能导致栈溢出。

五、 经典例题​

1：阶乘

题目： 求 n 的阶乘 n!

思路：

  • n! = n * (n-1)!
  • 0! = 1! = 1（基准）

示例：

输入：5 输出：120 5! = 54321 = 120

// 递归求阶乘
int factorial(int n) {
  if (n <= 1)
    return 1;
  return n * factorial(n-1);
}

2：斐波那契数列

题目： 求第 n 个斐波那契数

思路：

  • F(n) = F(n-1) + F(n-2)
  • F(0)=0, F(1)=1（基准）

示例：

序列：0, 1, 1, 2, 3, 5, 8, 13... 输入：6 输出：8

// 递归求斐波那契
int fib(int n) {
  if (n <= 1)
    return n;
  return fib(n-1) + fib(n-2);
}

注意：此解法存在大量重复计算，可用记忆化优化。

3：倒序数

题目： 输入非负整数，输出倒序数

思路：

  • 输出最后一位：n % 10
  • 递归处理前几位：n / 10
  • 基准：n == 0 时停止

示例：

输入：12345 输出：54321

// 递归输出倒序数
void reverse(int n) {
  if (n == 0) return;
  cout << n % 10;
  reverse(n / 10);
}

// 返回倒序数值
int revNum(int n, int r=0) {
  if (n == 0) return r;
  return revNum(n/10, r*10+n%10);
}

六、 递归的优缺点​

优点 ​

  • 代码简洁，逻辑清晰
  • 天然适合解决分治问题
  • 易于处理树形结构
  • 数学定义直接映射为代码

缺点 ​

  • 函数调用开销大，效率较低
  • 栈空间有限，可能导致溢出
  • 可能存在大量重复计算
  • 调试和理解难度较高

七、 总结与练习​

核心要点： 递归 = 基准条件 + 递归条件 + 向基准靠近

  • 写递归前先确定基准条件
  • 确保每次递归都向基准条件靠近
  • 注意栈溢出问题，必要时改用迭代

★ PPT课件