Skip to main content

三、递归算法

高考考点​

递归算法；

一、递归算法是什么​

递归可以比喻为：

  • 俄罗斯套娃
  • 镜像互照
  • 故事嵌套：从前有座山，山里有个庙，...

递归是一个特殊的函数。特殊在于递归函数总是在函数体内部调用自己。

  • 递：可以理解为向下传递。
    • 传递：传递子问题。子问题就是：把一个大问题拆解为：值(已确定) + 子问题(悬而未决)
    • 拆解：每次传递时，需拆解子问题，缩小子问题的规模。
    • 停止：需要决定在何时终止传递。也就是让函数停止调用自己。
  • 归：可以理解为向上归纳、合并。
    • 把所有确定的值归纳合并，就得到了最终结果。

二、递归三要素（重要！）​

  1. 递归调用：调用自己（处理里面的套娃）
  2. 递归条件：如何缩小问题？（打开当前套娃）
  3. 基线条件：什么时候停止？（最小的套娃）

四、递归示例​

示例1：阶乘（Factorial）​

什么是阶乘？

5! = 5 × 4 × 3 × 2 × 1 = 120
4! = 4 × 3 × 2 × 1 = 24
3! = 3 × 2 × 1 = 6
2! = 2 × 1 = 2
1! = 1
0! = 1 （规定）

递归思想：

要算 5!
= 5 × 4!
= 5 × 4 × 3!
= 5 × 4 × 3 × 2!
= 5 × 4 × 3 × 2 × 1!
= 5 × 4 × 3 × 2 × 1
= 120

C#代码：递归实现阶乘

using System;

class RecursionExample1
{
  static void Main(string[] args)
  {
    // 示例 1：阶乘
    Console.Write("请输入一个正整数：");
    int num = Convert.ToInt32(Console.ReadLine());
    if (num > 0)
    {
        int result = RecursionFn(num);
        Console.WriteLine(result);
    }
  }
  // 递归计算阶乘
  private static int RecursionFn(int n)
  {
    // 1. 什么时候停止？
    if (n == 0 || n == 1) return 1;
    // 2. 递归条件：如何缩小问题？
    return n *  RecursionFn(n - 1) ;
  }
}

输出结果（计算5!的过程）：

调用 Factorial(5)
  5! = 5 × 4!
调用 Factorial(4)
  4! = 4 × 3!
调用 Factorial(3)
  3! = 3 × 2!
调用 Factorial(2)
  2! = 2 × 1!
调用 Factorial(1)
  到达基线条件：Factorial(1) = 1
  计算完成：2 × 1 = 2
  计算完成：3 × 2 = 6
  计算完成：4 × 6 = 24
  计算完成：5 × 24 = 120
结果：120

示例2：求和递归​

题目：写出下面递归函数计算 Sum(5) 的完整过程

static void Main(string[] args)
{
    // 示例 1：求和
    Console.Write("请输入一个正整数：");
    int num = Convert.ToInt32(Console.ReadLine());
    if (num > 0)
    {
        int result = Sum(num);
        Console.WriteLine(result);
    }
}
private static int Sum(int n)
{
    if (n == 1) return 1;  // 基线条件
    return n + Sum(n - 1); // 递归调用
}

手动计算过程：

Sum(5)
= 5 + Sum(4)
= 5 + (4 + Sum(3))
= 5 + 4 + (3 + Sum(2))
= 5 + 4 + 3 + (2 + Sum(1))
= 5 + 4 + 3 + 2 + 1
= 15

答案：Sum(5) = 15

调用栈图示：

Sum(5)
  ↓
5 + Sum(4)
     ↓
   4 + Sum(3)
        ↓
      3 + Sum(2)
           ↓
         2 + Sum(1)
              ↓
             1 ← 基线条件

示例3：递归函数填空​

题目：补全递归打印数字的代码

void PrintNumbers(int n)
{
    if (______)  // 填空1：基线条件
    {
        return;
    }
    
    Console.Write(n + " ");  // 先打印当前数字
    ______;  // 填空2：递归调用
}

// 调用 PrintNumbers(5) 应该输出：5 4 3 2 1

答案：

// 填空1：n <= 0 或 n == 0
// 填空2：PrintNumbers(n - 1)

// 如果要输出 1 2 3 4 5，代码应该是：
void PrintNumbersAscending(int n)
{
    if (n <= 0) return;
    
    PrintNumbersAscending(n - 1);  // 先递归
    Console.Write(n + " ");        // 再打印
}

示例4：斐波那契数列（Fibonacci）​

什么是斐波那契数列？

斐波那契数列的开头两项固定（有两种常见表述，无本质区别），从第三项起，每一项的值 = 它的前一项 + 它的前前一项。

第0项：0
第1项：1
第2项：1（0+1）
第3项：2（1+1）
第4项：3（1+2）
第5项：5（2+3）
第6项：8（3+5）
第7项：13（5+8）
...
规律：F(n) = F(n-1) + F(n-2)

递归思想：

要算 F(5)
= F(4) + F(3)
= [F(3) + F(2)] + [F(2) + F(1)]
= ... 一直分解到 F(1) 和 F(0)

C#代码（带详细注释）：

using System;

class RecursionExample2
{
    static void Main()
    {
        // 斐波那契数列前10项
        Console.WriteLine("斐波那契数列：");
        Console.WriteLine("位置：0 1 2 3 4 5  6  7  8  9  10");
        Console.WriteLine("数值：0 1 1 2 3 5  8 13 21 34 55");
        
        Console.WriteLine("\n计算过程演示：\n");
        
        // 计算 F(5) 并显示过程
        int n = 5;
        int result = FibonacciWithTrace(n, "");
        Console.WriteLine($"\nF({n}) = {result}");
        
        // 计算前几个数
        Console.WriteLine("\n完整数列：");
        for (int i = 0; i <= 10; i++)
        {
            Console.Write($"{Fibonacci(i)} ");
        }
    }
    
    // 递归计算斐波那契数（带调用跟踪）
    static int FibonacciWithTrace(int n, string indent)
    {
        Console.WriteLine($"{indent}调用 Fibonacci({n})");
        
        // 1. 基线条件：什么时候停止？
        if (n == 0)
        {
            Console.WriteLine($"{indent}  基线条件：F(0) = 0");
            return 0;
        }
        if (n == 1)
        {
            Console.WriteLine($"{indent}  基线条件：F(1) = 1");
            return 1;
        }
        
        // 2. 递归条件：如何缩小问题？
        // F(n) = F(n-1) + F(n-2)
        Console.WriteLine($"{indent}  F({n}) = F({n-1}) + F({n-2})");
        
        // 3. 递归调用：自己调用自己（两次！）
        int left = FibonacciWithTrace(n - 1, indent + "  ");
        int right = FibonacciWithTrace(n - 2, indent + "  ");
        
        int result = left + right;
        Console.WriteLine($"{indent}  计算结果：F({n}) = {left} + {right} = {result}");
        
        return result;
    }
    
    // 普通的递归斐波那契函数
    static int Fibonacci(int n)
    {
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

写法 2：

class Program
{
    static void Main(string[] args)
    {
        // 测试：计算第10项（索引从0开始）
        int n = 10;
        long result = FibonacciRecursive(n);
        Console.WriteLine($"斐波那契数列第 {n} 项（递归实现）：{result}");
    }
    public static long FibonacciRecursive(int n)
    {
        // 递归出口：终止条件（n < 2 时直接返回n）
        if (n < 2) return n;
        // 递归体：调用自身，拆解为前两项之和
        return FibonacciRecursive(n - 1) + FibonacciRecursive(n - 2);
    }

    // 普通的递归斐波那契函数
    static int Fibonacci(int n)
    {
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

输出结果（计算F(5)的过程）：

调用 Fibonacci(5)
  F(5) = F(4) + F(3)
  调用 Fibonacci(4)
    F(4) = F(3) + F(2)
    调用 Fibonacci(3)
      F(3) = F(2) + F(1)
      调用 Fibonacci(2)
        F(2) = F(1) + F(0)
        调用 Fibonacci(1)
          基线条件：F(1) = 1
        调用 Fibonacci(0)
          基线条件：F(0) = 0
        计算结果：F(2) = 1 + 0 = 1
      调用 Fibonacci(1)
        基线条件：F(1) = 1
      计算结果：F(3) = 1 + 1 = 2
    调用 Fibonacci(2)
      F(2) = F(1) + F(0)
      调用 Fibonacci(1)
        基线条件：F(1) = 1
      调用 Fibonacci(0)
        基线条件：F(0) = 0
      计算结果：F(2) = 1 + 0 = 1
    计算结果：F(4) = 2 + 1 = 3
  调用 Fibonacci(3)
    F(3) = F(2) + F(1)
    调用 Fibonacci(2)
      F(2) = F(1) + F(0)
      调用 Fibonacci(1)
        基线条件：F(1) = 1
      调用 Fibonacci(0)
        基线条件：F(0) = 0
      计算结果：F(2) = 1 + 0 = 1
    调用 Fibonacci(1)
      基线条件：F(1) = 1
    计算结果：F(3) = 1 + 1 = 2
  计算结果：F(5) = 3 + 2 = 5

F(5) = 5

示例5：斐波那契的循环版本（更快）​

static int FibonacciLoop(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    
    int prev2 = 0;  // F(0)
    int prev1 = 1;  // F(1)
    int current = 0;
    
    for (int i = 2; i <= n; i++)
    {
        current = prev1 + prev2;  // F(i) = F(i-1) + F(i-2)
        prev2 = prev1;            // 更新F(i-2)
        prev1 = current;          // 更新F(i-1)
    }
    
    return current;
}

对比：

  • 递归F(40)：可能需要几秒（重复计算多）
  • 循环F(40)：瞬间完成（只计算一次）

五、递归的优缺点​

优点：

  1. 代码简洁：几行代码解决复杂问题
  2. 思路清晰：符合人类的思维方式
  3. 解决特定问题：适合树、图等结构

缺点：

  1. 可能很慢：如斐波那契的递归版本
  2. 可能栈溢出：递归太深会报错
  3. 重复计算：如F(3)在斐波那契中被计算多次

六、综合练习题​

练习题1：汉诺塔问题（经典递归）​

问题描述： 有三根柱子A、B、C。A柱上有n个盘子，从小到大叠放。要把所有盘子移动到C柱，要求：

  1. 每次只能移动一个盘子
  2. 大盘子不能在小盘子上面
  3. 可以借助B柱

递归思路：

移动n个盘子从A到C：
1. 移动n-1个盘子从A到B（借助C）
2. 移动第n个盘子从A到C
3. 移动n-1个盘子从B到C（借助A）

C#代码框架：

void Hanoi(int n, char from, char to, char aux)
{
    if (n == 1)  // 基线条件：只有一个盘子
    {
        Console.WriteLine($"移动盘子1从{from}到{to}");
        return;
    }
    
    // 递归步骤
    Hanoi(n - 1, from, aux, to);  // 填空1
    Console.WriteLine($"移动盘子{n}从{from}到{to}");
    Hanoi(n - 1, aux, to, from);  // 填空2
}

// 测试：3个盘子
Hanoi(3, 'A', 'C', 'B');

输出结果：

移动盘子1从A到C
移动盘子2从A到B
移动盘子1从C到B
移动盘子3从A到C
移动盘子1从B到A
移动盘子2从B到C
移动盘子1从A到C

练习题2：递归求最大公约数（GCD）​

题目：用递归实现辗转相除法求最大公约数

int GCD(int a, int b)
{
    if (______)  // 填空1
    {
        return a;
    }
    return GCD(______, ______);  // 填空2
}

// 测试：GCD(48, 18) = 6
// 因为：48 ÷ 18 = 2 余 12
//       18 ÷ 12 = 1 余 6  
//       12 ÷ 6 = 2 余 0

答案：

// 填空1：b == 0
// 填空2：b, a % b

// 完整代码：
int GCD(int a, int b)
{
    if (b == 0) return a;
    return GCD(b, a % b);
}

七、递归常见错误​

错误1：没有基线条件（无限递归）​

// ❌ 错误：会永远递归下去
int BadRecursion(int n)
{
    return n + BadRecursion(n - 1);  // 没有停止条件！
}
// 结果：栈溢出异常（StackOverflowException）

错误2：基线条件不对​

// ❌ 错误：基线条件永远达不到
int BadFactorial(int n)
{
    if (n == 0) return 1;  // 基线条件
    return n * BadFactorial(n + 1);  // 应该减1，不是加1！
}
// 调用 BadFactorial(5) → 无限递归

正确写法：​

// ✅ 正确
int GoodFactorial(int n)
{
    if (n == 0 || n == 1)  // 正确的基线条件
        return 1;
    return n * GoodFactorial(n - 1);  // 正确的递归调用
}

八、学习建议​

  1. 先理解三要素：基线条件、递归条件、递归调用
  2. 画调用图：在纸上画出递归调用过程
  3. 从小开始：先理解Factorial(3)，再理解更大的
  4. 对比学习：对比递归和循环的实现
  5. 注意栈深度：不要递归太深（通常不要超过1000层）

九、总结​

递归 = 基线条件（何时停） + 递归调用（调自己）

  • 阶乘递归：n! = n × (n-1)!
  • 斐波那契递归：F(n) = F(n-1) + F(n-2)
  • 关键：问题要能分解成更小的相同问题

记住：写递归函数时，先想基线条件，不然会无限递归！

什么时候使用递归？

当问题“长得像它自己的子问题”，而且子问题规模明显变小，递归就很适合

什么时候不该用递归？

明显的线性问题：求和、累加、简单遍历数组。(for 更安全、更快)