传习Chuanxi

递推算法的基本思想

递推算法的基本思想

掌握递推算法基本思想。

递推从已知初值出发，按固定规则一步步推出后续项，直到得到目标。与递归「自顶向下调用自身」不同，递推通常是自底向上填表或迭代，避免重复计算。斐波那契数列、走台阶方案数、简单数列求和都可用递推建模。

GESP 四级在 120 分钟笔试里，递推多出现在填空式单选或判断：能否用前几项推出下一项、递推与递归说法是否等价、初值缺了能否唯一确定答案。编程题若出现，规模一般不大，循环实现即可。

// 走台阶：到第 n 阶的方案数 = 到 n-1 的方案 + 到 n-2 的方案
int ways[10];
ways[1] = 1; ways[2] = 2;
for (int i = 3; i <= 9; ++i)
    ways[i] = ways[i-1] + ways[i-2];

抓住「当前状态能否由若干更早状态表示」，是识别递推题的钥匙。

下面代码采用递推算法来计算斐波那契数列 f(n)=f(n−1)+f(n−2)f(n) = f(n-1) + f(n-2)，则横线上应填写（ ）。

int fib(int n) {
    if (n == 0 || n == 1)
        return n;

    int f1 = 0;
    int f2 = 1;
    int result = 0;
    for (int i = 2; i <= n; i++) {
        ________________________________     // 在此处填入代码
    }
    return result;
}

递推是一种通过已知的初始值和递推公式，逐步求解目标值的算法。

递推是一种通过已知的初始值和递推公式，逐步求解目标值的算法。

以下关于递推算法基本思想的描述，正确的是（ ）。

以下程序中使用了递推方式计算阶乘（n!=1×2×…×nn! = 1 \times 2 \times \ldots \times n），计算结果正确。

int factorial(int n) {
    int res = 1;
    for (int i = 0; i < n; ++i) {
        res *= i;
    }
    return res;
}

递推是在给定初始条件下，已知前一项（或前几项）求后一项的过程。

给定函数 climbStairs(int n) 的定义如下，则 climbStairs(5) 的返回的值是（ ）。

int climbStairs(int n) {
    if(n <= 2) return n;
    int a = 1, b = 2;
    for(int i = 3; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

关于递推算法的描述，正确的是（ ）。