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()
    {
        Console.WriteLine("=== 递归计算阶乘 ===\n");
        
        // 测试几个阶乘
        TestFactorial(0, "0! 应该是 1（规定）");
        TestFactorial(1, "1! 应该是 1");
        TestFactorial(2, "2! 应该是 2");
        TestFactorial(3, "3! 应该是 6");
        TestFactorial(4, "4! 应该是 24");
        TestFactorial(5, "5! 应该是 120");
        
        // 让用户自己试
        Console.Write("\n你想算几的阶乘？输入数字：");
        if (int.TryParse(Console.ReadLine(), out int n) && n >= 0)
        {
            int result = Factorial(n);
            Console.WriteLine($"{n}! = {result}");
        }
    }
    
    // 递归计算阶乘
    static int Factorial(int n)
    {
        Console.WriteLine($"调用 Factorial({n})");
        
        // 1. 基线条件：什么时候停止？
        if (n == 0 || n == 1)  // 0! = 1, 1! = 1
        {
            Console.WriteLine($"  到达基线条件：Factorial({n}) = 1");
            return 1;  // 停止递归
        }
        
        // 2. 递归条件：如何缩小问题？
        // n! = n × (n-1)!
        int smaller = n - 1;
        Console.WriteLine($"  {n}! = {n} × {smaller}!");
        
        // 3. 递归调用：自己调用自己
        int resultOfSmaller = Factorial(smaller);
        
        // 得到小问题的结果后，计算当前问题的结果
        int result = n * resultOfSmaller;
        Console.WriteLine($"  计算完成：{n} × {resultOfSmaller} = {result}");
        
        return result;
    }
    
    static void TestFactorial(int n, string description)
    {
        Console.WriteLine($"\n{description}");
        Console.WriteLine($"{"".PadRight(30, '-')}");
        int result = Factorial(n);
        Console.WriteLine($"结果：{result}");
    }
}

输出结果（计算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：斐波那契数列（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()
    {
        Console.WriteLine("=== 递归计算斐波那契数列 ===\n");
        
        // 斐波那契数列前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);
    }
}

输出结果（计算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

五、递归的优缺点​

优点：​

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

缺点：​

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

六、递归vs循环​

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

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：理解递归调用过程​

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

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 ← 基线条件

练习题2：递归函数填空​

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

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 + " ");        // 再打印
}

八、综合练习题​

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

问题描述： 有三根柱子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

练习题4：递归求最大公约数（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)
  • 关键：问题要能分解成更小的相同问题

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