CSP-J 入门级 · CSP 2025 入门级第一轮 第 3 题

函数 calc(n) 的定义如下，则 calc(5) 的返回值是多少？（ ）

int calc(int n) {
    if (n <= 1) return 1;
    if (n % 2 == 0) return calc(n / 2) + 1;
    else return calc(n - 1) + calc(n - 2);
}

这题千万别直接硬算 calc(5)，会绕晕。核心心法是：先算出所有更小的值，像填表一样。算出 calc(4) 和 calc(3) 后，最后一步直接相加。记住，偶数只跳一步，奇数要拆成两个小问题。

最容易栽跟头的地方是：第一，看到 calc(5) 就盲目展开，结果在 calc(3) 和 calc(5) 的分支里反复横跳，把 calc(3) 重复算了好几次，最后数出来的结果往往偏大；第二，对偶数逻辑理解不深，以为偶数也要拆成两个，其实偶数只要算一次 n/2 再加 1 就行；第三，边界条件看错，n<=1 时直接返回 1，很多人会误以为 n=0 时还要继续算。

这道题考查的是递归函数的执行逻辑与递推计算能力，属于信息学竞赛中非常基础但极易出错的经典题型。命题人特别喜欢用这种‘偶数单步、奇数双步’的混合逻辑来挖坑，因为学生往往惯性思维，看到递归就以为要像斐波那契数列那样每次都拆成两个，从而在计算过程中重复劳动，导致结果错误。

拿到这类题，正确的思考心法必须明确：不要试图从最大的参数 n 直接展开去推导，那样会陷入递归树，重复计算量巨大且容易乱。正确的入手点是‘从最小参数开始递推’，也就是把递归的过程反过来，当成填表来做。我们要先搞清楚代码里到底在算什么。

先看代码逻辑： 当 n <= 1 时，直接返回 1，这是递归的终止条件（边界）。 当 n 是偶数时（n % 2 == 0），返回 calc(n / 2) + 1。这意味着偶数只需要做一次递归调用，规模减半，然后加 1。 当 n 是奇数时，返回 calc(n - 1) + calc(n - 2)。这意味着奇数需要拆成两个子问题，分别计算前一个和前两个的值，然后相加。

现在我们来一步步‘填表’，从最小的 n 开始往上推，直到算出 calc(5)：

1. 计算 calc(0) 和 calc(1)： 根据边界条件 n <= 1，直接返回 1。 所以，calc(0) = 1，calc(1) = 1。

2. 计算 calc(2)： 2 是偶数，触发 calc(2 / 2) + 1，也就是 calc(1) + 1。 代入 calc(1) = 1，得到 1 + 1 = 2。 所以，calc(2) = 2。

3. 计算 calc(3)： 3 是奇数，触发 calc(3 - 1) + calc(3 - 2)，也就是 calc(2) + calc(1)。 代入已知的 calc(2) = 2，calc(1) = 1，得到 2 + 1 = 3。 所以，calc(3) = 3。

4. 计算 calc(4)： 4 是偶数，触发 calc(4 / 2) + 1，也就是 calc(2) + 1。 代入 calc(2) = 2，得到 2 + 1 = 3。 所以，calc(4) = 3。（注意这里很多人会误以为偶数也要拆，其实偶数只加 1，非常关键）

5. 计算 calc(5)： 5 是奇数，触发 calc(5 - 1) + calc(5 - 2)，也就是 calc(4) + calc(3)。 代入已知的 calc(4) = 3，calc(3) = 3，得到 3 + 3 = 6。 所以，calc(5) = 6。

整个计算过程非常清晰，每一步都依赖前面已经算好的小数值，完全避免了重复计算。最终答案就是 6，对应选项 B。

关于这个考点的考频与趋势：在题库中，递归函数共出现过 115 题，覆盖 8 个考试级别，分布非常广泛。从年份上看，2007-2014 年间考得比较零散，但近年来热度明显上升。特别是 2024 年考了 25 题，2025 年考了 15 题，2026 年预测考了 18 题，呈现明显的上升趋势。在分赛事维度，CSP 入门级考了 32 题，GESP 五级考了 35 题，说明这个知识点在入门阶段是重中之重。

基于数据预测：鉴于 2024 年和 2025 年递归类题目数量激增，且 2026 年预测数据也较高，可以判断未来 1-2 年内，这类题目在 CSP 入门级和 GESP 五级考试中仍将是高频考点。命题人可能会继续采用‘混合逻辑’（如本题的偶数单步、奇数双步）来增加区分度，或者结合数组、循环等结构考察递归的变体。建议同学们务必熟练掌握‘从底向上递推’的解题思路，这是应对此类题目的万能钥匙。