递推

概念讲解

什么是递推？

递推是通过已知条件，逐步推导出未知结果的算法思想。

递推 vs 递归

特性 递推 递归
方向 从前往后 从后往前
实现 循环 函数调用
效率 高 低（可能重复计算）

经典递推模型

1. 斐波那契数列

F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)

12345678910int fib(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

2. 台阶问题

问题： 一次可以走 1 级或 2 级台阶，上 n 级台阶有多少种走法？

f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)

3. 过河卒

问题： 棋盘上从左上角到右下角，只能向右或向下走，有多少条路径？

f(i,j)=f(i−1,j)+f(i,j−1)f(i, j) = f(i-1, j) + f(i, j-1)

123456789int paths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 1));
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

考点分析

初赛考查方式

  1. 选择题： 递推关系
  2. 程序阅读： 递推程序
  3. 编程题： 递推应用

常见考点

  • 斐波那契数列
  • 台阶问题
  • 路径计数

例题精讲

例题 1：斐波那契

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

解答：

F(0)=0,F(1)=1,F(2)=1,F(3)=2,F(4)=3,F(5)=5F(0)=0, F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5

答案是 5。

例题 2：台阶问题

题目： 上 4 级台阶有多少种走法？

解答：

f(1)=1,f(2)=2,f(3)=3,f(4)=5f(1)=1, f(2)=2, f(3)=3, f(4)=5

答案是 5 种。

练习题

  1. 斐波那契数列的前 10 项是什么？
查看答案

前 10 项（从第 0 项开始）：

n 0 1 2 3 4 5 6 7 8 9
F(n) 0 1 1 2 3 5 8 13 21 34

递推公式：F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)

  1. 上 5 级台阶有多少种走法？
查看答案

8 种

台阶数 1 2 3 4 5
走法数 1 2 3 5 8

递推公式：f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)

（最后一步走 1 级或 2 级）

  1. 3×3 的棋盘从左上角到右下角有多少条路径？
查看答案

6 条

使用递推：f(i,j)=f(i−1,j)+f(i,j−1)f(i,j) = f(i-1,j) + f(i,j-1)

0 1 2
0 1 1 1
1 1 2 3
2 1 3 6

易错点

⚠️ 注意：

  1. 递推是从前往后计算
  2. 注意初始值的设定
  3. 递推通常比递归效率高
  4. 注意整数溢出问题