CSP-J 入门级 · CSP 2020 入门级第一轮 第 6 题

设 $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 的输出是什么？（）。

这题是递归找最小值的经典模型。拿到题别急着看选项，先盯着递归的‘终止条件’和‘返回值’。当 n=1 时直接返回 A[1]，这是递归的‘底座’；之后每次把前面 n-1 个的最小值（记作 temp）和当前 A[n] 比，谁小返回谁。顺着这个逻辑推两三个样例，答案自然就出来了。

最容易栽跟头的地方是看错比较方向。题目里写的是‘if temp < A[n] then return temp else return A[n]’，意思是只要前面的最小值比当前元素小，就保留前面的；只有当前面已经比当前元素大了，才换当前元素。很多学生会下意识以为这是在找最大值，或者看到‘temp’就以为是累加求平均，完全忽略了‘递归返回的是极值’这个核心语义。另外，有些同学会纠结递归会不会死循环，其实只要 n 每次减 1 且底数 n=1 有返回值，递归深度就是 O(n)，完全可控。

这道题考查什么：递归函数的逻辑分析——通过递归调用逐步缩小问题规模，并在每一步做局部比较，最终收敛到全局极值。这是 CSP 入门级非常典型的‘递归找极值’模型。

把概念讲人话：递归函数 XYZ(A[1..n]) 的作用很明确：它负责找出数组前 n 个元素里的最小值。怎么实现的呢？它分两步走：第一步是‘打地基’，当 n=1 时，数组只有一个数 A[1]，那最小值肯定就是 A[1]，直接返回；第二步是‘递推’，当 n>1 时，它先递归调用自己处理前 n-1 个元素，得到一个临时结果 temp（这个 temp 就是前 n-1 个元素的最小值），然后拿这个 temp 和当前元素 A[n] 做个比较：如果 temp 比 A[n] 小，说明前 n-1 个里已经找到更小的了，那整体最小值还是 temp；如果 temp 不比 A[n] 小（也就是 A[n] 更小或相等），那整体最小值就得换成 A[n]。最后返回这个较小的那个数。

命题人怎么挖坑：这道题的陷阱主要在‘比较方向’和‘返回值语义’上。命题人故意把条件写成‘if temp < A[n] then return temp else return A[n]’，这跟找最大值的逻辑（if temp > A[n] then return temp else return A[n]）正好相反。很多学生看到‘temp’就以为是累加求和，或者看到‘递归’就以为是排序，完全没意识到这是在找极值。此外，有些同学会纠结‘递归会不会重复计算’，其实这里每次递归只返回一个数，没有重复计算的问题，复杂度就是 O(n)。

思考心法：拿到题先想什么？ 1. 先看终止条件：n=1 时返回 A[1]，这是递归的‘底座’，任何递归问题都必须有个明确的终止点，否则就是死循环。 2. 再看递归步骤：n>1 时，它先算出前 n-1 个的最小值 temp，然后拿 temp 和 A[n] 比，谁小返回谁。这其实就是‘分治’思想的简化版：把大问题拆成小问题，小问题解决后再合并结果。 3. 最后看返回值：XYZ 返回的是‘较小者’，所以整体就是全局最小值。

一步步推演（用一个小例子）：假设 A = [5, 3, 4]，n=3。

• 调用 XYZ(1..3)：

- temp = XYZ(1..2) - 调用 XYZ(1..2)： - temp = XYZ(1..1) = A[1] = 5 - 比较 temp(5) 和 A2：5 < 3？不成立，所以返回 A[2] = 3 - 回到 XYZ(1..2)，得到 temp = 3 - 比较 temp(3) 和 A2：3 < 3？不成立（相等），返回 A[2] = 3 - 回到 XYZ(1..3)，得到 temp = 3 - 比较 temp(3) 和 A3：3 < 4？成立，返回 temp = 3

• 最终 XYZ(1..3) 返回 3，正好是数组的最小值。

一般性证明（归纳法）：

• 基础情况：n=1 时，XYZ 返回 A[1]，显然正确。
• 归纳假设：假设对于任意 k < n，XYZ(A[1..k]) 返回的是前 k 个元素的最小值。
• 归纳步骤：考虑 n 的情况。XYZ 先递归得到 temp = XYZ(A[1..n-1])，根据假设，temp 就是前 n-1 个元素的最小值。然后比较 temp 和 A[n]：

- 如果 temp < A[n]，说明前 n-1 个里已经有更小的了，整体最小值就是 temp； - 否则（temp ≥ A[n]），说明 A[n] 比前面所有都小（或相等），整体最小值就是 A[n]。

• 因此，XYZ(A[1..n]) 返回的是 min(temp, A[n]) = min(前 n-1 个最小值, 第 n 个) = 前 n 个元素的最小值。归纳完成。

避坑提醒：

• 千万别把‘temp < A[n]’看成‘temp 比 A[n] 大’，这是找最大值的条件，容易选错 C 或 D。
• 也别以为这是在求平均值，题目里没有任何累加操作，只是比较大小。
• 递归深度是 n，如果 n 特别大（比如 10^5），在 C++/Java 里可能会栈溢出，但 CSP 入门级通常 n 不会太大，而且题目只问返回值，不涉及实现细节，所以不用纠结性能问题。

考频与趋势：

• ‘函数定义与调用’这个知识点在题库里共考过 70 题，覆盖 9 个考试级别。从逐年分布看：2023 年考了 15 题、2024 年 17 题、2025 年 23 题，呈现明显的上升趋势；2026 年也有 6 题。分赛事来看，GESP 四级（23 题）、五级（19 题）、六级（8 题）和 CSP 入门级（7 题）是重灾区，说明这类基础递归题在入门阶段非常常见。
• ‘递归函数’单独考过 115 题，覆盖 8 个级别。逐年分布：2024 年 25 题、2025 年 15 题、2026 年 18 题，同样在高位运行；GESP 五级（35 题）和 CSP 入门级（32 题）是绝对主力。

未来预测： 基于上述数据，递归相关题目在 2024-2026 年已经进入高频区，尤其是 GESP 五级和 CSP 入门级。考虑到 2025 年函数定义与调用考了 23 题（近五年最高），而 2026 年递归函数考了 18 题（略低于 2025 年的 15 题，但整体仍很高），可以合理推测：未来几年这类‘递归找极值’的题型仍会保持较高频率，命题人可能会在 GESP 五级或 CSP 入门级继续出类似的递归逻辑分析题，难度可能略有提升（比如嵌套递归或带参数传递），但核心思想不会变——依然是考察学生能否看懂递归的终止条件和返回值语义。

总结：这道题的答案就是 B（数组的最小值）。解题的关键在于抓住递归的‘底座’（n=1 返回 A[1]）和‘递推’（比较 temp 和 A[n]，取小者），不要被‘temp’或‘递归’这些词带偏。只要按这个逻辑推一遍，答案一目了然。