递归函数

概念讲解

什么是递归？

递归是函数调用自身的过程。

递归三要素

  1. 边界条件： 递归终止的条件
  2. 递推关系： 大问题和小问题的关系
  3. return 返回值： 返回结果

经典递归模型

阶乘

1234int factorial(int n) {
    if (n <= 1) return 1;  // 边界条件
    return n * factorial(n - 1);  // 递推关系
}

斐波那契数列

1234int fibonacci(int n) {
    if (n <= 1) return n;  // 边界条件
    return fibonacci(n - 1) + fibonacci(n - 2);  // 递推关系
}

汉诺塔

123456789void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        cout << "Move disk 1 from " << from << " to " << to << endl;
        return;
    }
    hanoi(n - 1, from, aux, to);
    cout << "Move disk " << n << " from " << from << " to " << to << endl;
    hanoi(n - 1, aux, to, from);
}

递归调用栈

示例

1234int f(int n) {
    if (n == 0) return 0;
    return f(n - 1) + 1;
}

调用栈

f(3) 调用 f(2)
f(2) 调用 f(1)
f(1) 调用 f(0)
f(0) 返回 0
f(1) 返回 1
f(2) 返回 2
f(3) 返回 3

考点分析

初赛考查方式

  1. 选择题： 递归概念
  2. 程序阅读： 递归执行过程
  3. 填空题： 递归返回值

常见题型

  • 递归执行过程
  • 递归返回值
  • 递归应用

例题精讲

例题 1：阶乘

题目： 求 5 的阶乘。

解答：

factorial(5) = 5 * factorial(4)
             = 5 * 4 * factorial(3)
             = 5 * 4 * 3 * factorial(2)
             = 5 * 4 * 3 * 2 * factorial(1)
             = 5 * 4 * 3 * 2 * 1
             = 120

例题 2：斐波那契数列

题目： 求第 5 个斐波那契数。

解答：

fibonacci(5) = fibonacci(4) + fibonacci(3)
             = (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
             = ...
             = 5

练习题

  1. 求 1~n 的和（递归）。
查看答案
1234int sum(int n) {
    if (n == 1) return 1;  // 边界条件
    return n + sum(n - 1);  // 递推关系
}
  1. 求 a 的 n 次方（递归）。
查看答案
1234long long power(int a, int n) {
    if (n == 0) return 1;  // 边界条件
    return a * power(a, n - 1);  // 递推关系
}
  1. 求最大公约数（递归）。
查看答案
1234int gcd(int a, int b) {
    if (b == 0) return a;  // 边界条件
    return gcd(b, a % b);  // 递推关系（辗转相除法）
}

易错点

⚠️ 注意：

  1. 递归必须有边界条件
  2. 递归要有递推关系
  3. 递归可能导致栈溢出
  4. 递归效率可能较低