递推法与递归法

递推法；递归法。

概念

递推从已知初值出发，用公式或规则由前若干项推出下一项，通常是自底向上的循环填表。递归把问题拆成规模更小的同类子问题，函数调用自身，是自顶向下的描述；若子问题重叠，需记忆化或改写成递推。本叶子考的是算法建模（状态转移、递归出口、递推式），与 cspj.cpp.recursion（C++ 递归函数语法、栈、参数传递）相邻但不同：后者问「这段递归代码输出什么」，前者问「问题能否用 f(n) 与 f(n-1) 表示」。与 cspj.algo.dp-basic 区分：简单递推常只有一维前后依赖，DP 可能有多维状态与取最值。

CSP-J 常考

cspj-r1-2019 第 30–31 题：阅读程序，根据递推或递归关系求某项或输出序列。
cspj-r1-2020 第 6 题：单选题，判断递推式、初值或递归深度相关说法。
cspj-r1-2022 第 22、24 题：阅读程序，手写 trace 递推数组或递归调用过程。
cspj-r1-2025 第 8 题：单选题，考查递推与递归概念或简单数列模型。

// 斐波那契：递推写法（初赛规模常用）
int f[20];
f[1] = f[2] = 1;
for (int i = 3; i <= n; ++i)
    f[i] = f[i-1] + f[i-2];
// 递归写法需写出口 n<=2，否则栈溢出

易错点

初值下标从 0 还是从 1 开始，与题面定义不一致会导致全错。
递归无出口或出口条件写错，阅读程序题里要数清「还会不会继续调用」。
把递推式写错一位：例如用 f[i-2] 写成 f[i-1]，完善程序空位只填一项时尤其要看清下标。

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

#include <iostream>using namespace std;const int maxn = 10000;int n;int a[maxn];int b[maxn];int f(int l, int r, int depth) { if (l > r) return 0; int min = maxn, mink; for (int i = l; i <= r; ++i) { if (min > a[i]) { min = a[i]; mink = i; } } int lres = f(l, mink - 1, depth + 1); int rres = f(mink + 1, r, depth + 1); return lres + rres + depth * b[mink];}int main() { cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 0; i < n; ++i) cin >> b[i]; cout << f(0, n - 1, 1) << endl; return 0;}

30单选3 分
当 $n=100$ 时，最坏情况下，与第 $12$ 行的比较运算执行的次数最接近的是：（）。

A
5000

B
600

C
6

D
100

阅读程序共 3 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

31单选3 分
当 $n=100$ 时，最好情况下，与第 $12$ 行的比较运算执行的次数最接近的是：（）。

A
100

B
6

C
5000

D
600

设 $A$ 是 $n$ 个实数的数组，考虑下面的递归算法：

XYZ (A[1..n])
1.  if n=1 then return A[1]
2.  else temp ← XYZ (A[1..n-1])
3.  if temp < A[n]
4.  then return temp
5.  else return A[n]

请问算法 XYZ 的输出是什么？（）。

A 数组的平均

A 数组的最小值

A 数组的中值

A 数组的最大值

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

1 #include <algorithm>2 #include <iostream>3 #include <limits>4 5 using namespace std;6 7 const int MAXN = 105;8 const int MAXK = 105;9 10 int h[MAXN][MAXK];11 12 int f(int n, int m)13 {14 if (m == 1) return n;15 if (n == 0) return 0;16 17 int ret = numeric_limits<int>::max();18 for (int i = 1; i <= n; i++)19 ret = min(ret, max(f(n - i,m), f(i - 1, m - 1)) + 1);20 return ret;21 }22 23 int g(int n, int m)24 {25 for (int i = 1;i <= n; i++)26 h[i][1]= i;27 for (int j = 1;j<= m; j++)28 h[0][j]= 0;29 30 for (int i= 1; i <= n; i++){31 for (int j= 2; j <= m; j++){32 h[i][j] = numeric_limits<int>::max();33 for (int k = 1;k <= i;k++)34 h[i][j]= min(35 h[i][j],36 max(h[i - k][j],h[k - 1][j - 1]) +1);37 }38 }39 40 return h[n][m];41 }42 43 int main()44 {45 int n,m;46 cin >> n>> m;47 cout << f(n, m) << endl << g(n, m)<< endl;48 return 0;49 }

22判断1.5 分
当输入为 7 3 时，第 $19$ 行用来取最小值的 min 函数执行了 $449$ 次。

阅读程序共 1.5 分1 道小题

整组作答后提交批改，成绩计入掌握度 · 已答 0/1

程序

24判断1.5 分
当 $m$ 为 $1$ 时，输出的第一行总为 $n$ 。

已知 $f[0] = 1$ , $f[1] = 1$ ，并且对于所有 $n \geq 2$ 有 $f[n] = (f[n-1] + f[n-2]) \% 7$ 。那么 $f[2025]$ 的值是多少？

$2$

$4$

$5$

$6$