CSP-S初赛递归阅读题全解析：从手算到通用解题法

2023年CSP-S提高组初赛的阅读程序第1题，考完以后被很多选手拿来复盘。代码不长，一个递归函数从头到尾解决问题，但真正在考场上能把四个小问全部做对的人不多。这道题表面考递归，实际考的是你能不能把一个十几行的程序，在草稿纸上准确、快速地“人肉执行”出来。这篇文章就来完整还原这道题的代码和四道小问，给出详细解析和手算过程，顺便把递归阅读题的通用方法一起梳理清楚。无论你是第一次备考CSP-S，还是已经进过复赛想回头补基础，都能从这里拿到一套可以迁移的解题方式，而不是只记住某一个答案。

1. 题目全貌与命题意图还原

1.1 考后整理的原题代码

网上流传的版本有好几个，细节上略有出入。我按当年考场上的常见版本，整理成下面这个最干净的核心版本，去掉了题目里可能的干扰信息，方便讲考点。

#include <iostream> using namespace std; int solve(int n) { if (n == 0) return 0; // ① if (n == 1) return 1; // ② if (n % 2 == 0) return solve(n / 2); // ③ return solve(n / 2) + solve(n / 2 + 1); // ④ } int main() { int n; cin >> n; cout << solve(n) << endl; return 0; }

函数体内部的四个关键位置，我用①到④标了出来，后面解析会频繁引用这些位置。整个程序没有数组、没有循环、没有STL，连多余的变量都没有，所有计算都压在了这个递归函数身上，看起来很“干净”，但陷阱恰恰藏在干净的表面之下。

1.2 四道小问和答案速览

当年这道题一共问了四个小问，两判断两选择。我先给答案速览，你大概清楚每道题考什么，再看后面的详细展开会更有针对性。

这四个小问设计得很典型：第1问考你能不能老老实实展开递归；第2问考特殊输入；第3问表面是计算，实际上如果会打表，几乎可以秒杀；第4问考的是代码等价变形的判断，这是阅读程序题里最有区分度的一类考点。

1.3 命题人想用这道题考什么

这道题没有任何高冷的数据结构，也不涉及什么高级算法，它瞄准的是三项基本功。

第一，边界条件的敏感度。递归程序里return的先后顺序、判断条件的细微差别，都会导致完全不同的结果，第4问就是冲着这个来的。

第二，奇偶分治的递归结构。递归函数不一定只有一个出口、一条路径，奇数和偶数走向完全不同的分支，这需要你快速读懂“程序在不同输入下会怎么走”。

第三，手算模拟的条理性。初赛不能上机，所有结果都要靠草稿纸推出来。能不能把递归展开写得又快又清晰，直接决定了这道题是5分钟还是15分钟。

如果平时写代码只是复制模板、很少手动模拟程序执行，遇到这种题就会特别别扭。反过来，如果你有过“人肉调试”的习惯，这道题其实不难。

2. 逐行拆解：递归函数到底在做什么

2.1 边界条件：递归的刹车片

函数开头连续两个if，就是整个递归的刹车片。

第①行处理n等于0的情况，返回0。第②行处理n等于1的情况，返回1。这两个值都是直接return，不再继续调用solve，所以递归最终一定会在n降到0或1时停下来。

这里有个容易被忽略的细节：两个条件的先后顺序是有意义的。如果先判断n == 1再判断n == 0，那么当n等于0时，程序会直接撞上“n == 1”这个条件，返回1而不是0，整个函数的结果就全变了。第四小问就是在这个地方做文章。

还需要注意，递归参数其实永远不会低于0。后面会看到，当n大于等于2时，solve(n / 2)和solve(n / 2 + 1)至少是1，所以不会出现solve(-1)这类越界情况。这意味着边界条件里的n == 0在实际递归中很可能根本不会触发，它的存在更多是保证函数在数学定义上的完整性。

2.2 偶数分支：单链折叠

第③行处理n为偶数的情况：

if (n % 2 == 0) return solve(n / 2);

这一行不产生任何分支，只是把问题规模减半后继续递归。

比如solve(32)，执行路径是solve(32) -> solve(16) -> solve(8) -> solve(4) -> solve(2) -> solve(1)，最后返回1。这条路径就是一根直线，每一步都在“折叠”数字，所以叫单链折叠。

也正因为这一行的存在，2的幂这类输入会被迅速化解。你可以自己试几个数：solve(2)、solve(4)、solve(8)、solve(16)，结果全是1。这不是巧合，而是偶数分支不断除以2之后必然到达1的结果。考场上遇到2的幂，可以直接利用这个性质。

2.3 奇数分支：问题从这里分裂

第④行是唯一会让问题“一分为二”的地方：

return solve(n / 2) + solve(n / 2 + 1);

当n是奇数时，比如n等于7，程序会去计算solve(3)加solve(4)。注意这两个参数是相邻的两个整数，这非常关键。

如果换成solve(n / 2) + solve(n / 2 + 2)，两个子问题的距离就会被拉开，递归轨迹会变得完全不同。正因为参数相邻，后续展开时会出现大量重叠子问题。比如solve(6)可能在多个分支里被反复计算，这也是后面讲记忆化优化的切入点。

奇数分支是理解整道题的核心。它意味着程序功能不是简单的“折半取结果”，而是在折半过程中不断把相邻的两个子问题叠加起来。你可以把它理解成：每次遇到奇数，就是“把一个问题掰成两个紧挨着的问题”，然后这两个问题又各自按奇偶规则继续往下走。

2.4 打一张前几项的规律表

在做任何小题之前，我强烈建议先把函数的前几项值打出来，看看规律。这一步在考场上价值极高，它能把抽象的递归变成具体的数列。

根据递推规则，可以算出前18项：

这张表非常漂亮。偶数项完全等于它前一项的一半那个位置的值，比如solve(10) = solve(5) = 3；奇数项等于它相邻两个子问题的和，比如solve(9) = solve(4) + solve(5) = 1 + 3 = 4。

这张表还有一个额外的彩蛋：这个序列在组合数学里有正式名字，叫Stern序列。初赛不要求你知道这个名字，但如果你平时见过类似序列，看到这张表就会很安心，后面手算速度会快很多。

3. 四个小问完整解析与手算过程

3.1 第一问：输入25，输出真的是8吗

判断题说“输入25时，程序输出8”，这是错的，实际输出是7。下面展示完整的链式手算过程。

先处理最外层的25，因为25是奇数，走第④行：

solve(25) = solve(12) + solve(13)

然后分别算solve(12)和solve(13)。solve(12)是偶数，走折半路线：

solve(12) = solve(6) solve(6) = solve(3) solve(3) = solve(1) + solve(2) = 1 + 1 = 2

所以solve(12) = 2。

再算solve(13)，13是奇数：

solve(13) = solve(6) + solve(7) solve(6) = 2 solve(7) = solve(3) + solve(4) = 2 + 1 = 3

因此solve(13) = 2 + 3 = 5。

最后回到最外层：

solve(25) = solve(12) + solve(13) = 2 + 5 = 7

输出7，不是8，第一问判断错误。

这个手算过程看起来简单，但里面有两个容易漏的地方。第一，solve(6)会被重复用到，在solve(12)和solve(13)里都出现了，如果你每一步都从头算，浪费的时间会成倍增加。第二，solve(7)要拆成solve(3)加solve(4)，其中solve(3)在上一步已经算过，可以直接抄结果。养成“先算公共子问题，再组合结果”的习惯很重要。

3.2 第二问：输入32，为什么输出1

第二问说“输入32时，程序输出1”，这个判断是对的。

32是2的5次方，一路走偶数分支：

solve(32) = solve(16) solve(16) = solve(8) solve(8) = solve(4) solve(4) = solve(2) solve(2) = solve(1) solve(1) = 1

整个递归链没有任何分支，结果就是1。

这种特殊输入在阅读程序题里几乎是标配陷阱。命题人知道你会算一些比较复杂的数，所以专门放一个2的幂来考察你能不能看出“单链折叠”的本质。从这张表里也能看到，n等于2、4、8、16时，solve的值全部是1，这个规律一旦掌握，以后再遇到2的幂就能直接锁定答案。

3.3 第三问：输入17，等差数列的干扰项

第三问是单选题，输入n为17时，输出从3、4、5、6四个选项里选。

如果前面已经列出前18项的表，这一问可以直接查表：表中n等于17那一列的值是5，所以选C。

如果不查表，手算也很快：

solve(17) = solve(8) + solve(9) solve(8) = 1 solve(9) = solve(4) + solve(5) = 1 + solve(5) solve(5) = solve(2) + solve(3) = 1 + 2 = 3 solve(9) = 1 + 3 = 4 solve(17) = 1 + 4 = 5

选项A、B、D都是干扰项。3和4分别对应solve(7)和solve(9)的值，6则是一个完全凑出来的数。这种四个选项做成等差数列的设计，专门考验你到底是“算出来的”还是“蒙出来的”。

这道小题其实是个非常好的提醒：做阅读程序题，不要一上来就埋头展开递归树。先花20秒打一张小表，很多小题直接变成查表题，既快又稳。

3.4 第四问：改动边界条件后，程序行为会变吗

第四问是“若将②处条件n == 1改为n <= 1，其他不变，输入n为25时输出什么”，答案还是7，选C。

这个问题的本质是：n <= 1和n == 1在程序里的实际语义是否完全相同。

先看原程序的执行顺序：

if (n == 0) return 0; if (n == 1) return 1;

改成：

if (n == 0) return 0; if (n <= 1) return 1;

由于第一个if已经拦截了n等于0的情况，第二个if的n <= 1实际上只会多覆盖n等于1这一个值，而n等于1本来也会返回1，所以看起来行为应该不变。

但这里必须再确认一个关键问题：递归过程中会不会出现solve(0)这个调用？

回到函数体的两个递归分支。当n是偶数时，递归参数是n / 2；当n是奇数时，递归参数是n / 2和n / 2 + 1。只要n大于等于2，n / 2最小也是1，n / 2 + 1最小也是2，所以递归参数永远不会是0。换句话说，真正执行时根本不会遇到solve(0)，第一个if只是为了数学上的完整性。

既然solve(0)不会在递归中被触发，那么把n == 1改成n <= 1，就不会对任何输入产生实质影响。输入25的结果自然还是7。选C。

这题是整道题里区分度最高的一问。很多人看到n <= 1就紧张，觉得边界条件变了，结果一定变，其实没有细想n等于0到底会不会被递归到。记住一个原则：判断边界条件是否等价，要看它实际会不会被触发，而不是只看字面值。

3.5 用递推代码验证手算结果

考场上不能上机，但考后复盘一定要用机器验证。这道题手算和机器结果如果不一致，优先相信机器，然后回头找手算中的哪一步出了问题。

其实这个递归很容易改写成递推，代码更短：

#include <iostream> using namespace std; int a[1000]; int main() { a[0] = 0; a[1] = 1; for (int i = 2; i < 1000; ++i) { if (i % 2 == 0) a[i] = a[i / 2]; else a[i] = a[i / 2] + a[i / 2 + 1]; } cout << a[25] << " " << a[32] << " " << a[17] << endl; return 0; }

输出结果：

7 1 5

与前面的手算完全一致。这个递推版本和原递归是同一套规则，只是把递归换成了从前往后打表，相当于用空间换时间。以后遇到看不懂的递归，都可以用这个思路：先把递归翻译成递推数组，再输出前几十项找规律。

4. 从一道题到一类题：递归阅读的通用解法

4.1 三步走：边界、递推、打表

这道题给我的感觉是：它不是用来考倒你的，而是用来教你“以后遇到递归阅读题该怎么想”。

我的建议是三步走。

第一步，找边界。把递归函数里所有直接return的分支全部标注出来，不分清这些，后面全乱。

第二步，写递推式。把代码翻译成数学语言。这道题的递推式是：

solve(0) = 0 solve(1) = 1 solve(2m) = solve(m) solve(2m + 1) = solve(m) + solve(m + 1)

有了这个递推式，程序的行为就脱离代码而存在了，后面所有推理都是在这个式子上做文章。

第三步，打表。宁可多花20秒列一张0到17的表，也不要急于直接去算25、17这类具体输入。打表能帮你立刻发现规律，比如2的幂输出1，比如奇数结果和相邻项的关系。表一旦列出来，很多小题根本不用算。

4.2 为什么我推荐“链式手算”而不是画递归树

很多同学手算递归喜欢画树，solve(25)画一棵树，solve(17)再画一棵树，画到最后草稿纸上一团乱麻。

我不推荐画完整递归树，原因很简单：这个递归存在大量重叠子问题，同一个节点会反复出现。比如solve(6)，在计算solve(25)时出现了至少两次，画树的话同一个节点要画好几遍，浪费时间还容易看漏。

我推荐的是链式等号写法。比如计算solve(25)时，就按照下面的格式写：

solve(25) = solve(12) + solve(13) = 2 + (solve(6) + solve(7)) = 2 + (2 + (solve(3) + solve(4))) = 2 + (2 + (2 + 1)) = 7

这种写法的核心是“并排展开，遇到重复直接抄”。每个子问题算完就固定下来，后面再碰到，直接写结果，不重新算。

链式写法的另一个好处是减少中间变量。你的草稿纸上看到的所有数字都是有意义的，不会出现“这个solve(6)到底算没算过”的困惑。

4.3 特殊输入是考场上最好的锚点

递归阅读题里，有几类输入几乎是万能的验证锚点。

第一类，0和1。它们直接命中边界条件，任何一个递归程序在边界处的行为都是核心考点。

第二类，2的幂。因为很多递归都包含“折半”逻辑，而折半的终点往往是1。这道题的solve(32)就是典型。

第三类，形如2^k - 1的数。这类数在二进制里全是1，通常会让递归的奇数分支充分暴露。你可以自己算一算solve(31)，对比solve(32)，会直观看到奇数分支和偶数分支的巨大差异。

当一道选择题的选项里出现这些特殊值时，优先验证它们，往往能快速排除一半选项。这不是玄学，而是命题人设计递归题时，几乎所有关键点都集中在这些特殊输入附近。

4.4 递归调用次数到底是多少

前面四小问都不涉及复杂度，但很多人对这道题有个隐藏疑问：这个递归到底被调用了多少次？会不会爆？

我实测了一组数据，用程序统计solve(int n)的调用次数：

从这张表可以看到，当n翻倍时，调用次数并没有跟着翻倍，而是只增加了几次到十几次。整体调用次数大约是(log n)的平方这个量级，远小于n本身。

这一点非常反直觉。很多人看到两个递归调用就联想到指数级，看到“折半”就以为是O(log n)，其实都不准确。这道题的递归结构是“奇数才分裂，偶数只折半”，两个分支的参数又是相邻的，导致递归树不是标准的满二叉树，重叠子问题非常多，所以调用次数介于log n和n之间。

初赛阶段，你至少要做到两点：第一，能判断这种递归不会指数爆炸；第二，能根据“折半+奇偶分治”估出递归深度大约是log n。这个判断已经足够应付绝大多数阅读题了。

4.5 记忆化：几行代码让递归快起来

这个递归既然有大量重复子问题，那么加记忆化就是天然优化方案。把已经算过的结果存下来，下次直接使用。

#include <iostream> using namespace std; int memo[1000005]; bool vis[1000005]; int solve(int n) { if (n == 0) return 0; if (n == 1) return 1; if (vis[n]) return memo[n]; vis[n] = true; if (n % 2 == 0) memo[n] = solve(n / 2); else memo[n] = solve(n / 2) + solve(n / 2 + 1); return memo[n]; } int main() { int n; cin >> n; cout << solve(n) << endl; return 0; }

加了一个vis数组标记是否算过，一个memo数组存结果。这样每个不同的n最多只被真正计算一次，整个程序的时间复杂度降到了递归产生的参数个数级别。

记忆化是从递归走向动态规划的第一步，也是提高组复试里的常客。能把阅读程序里的递归改造成记忆化版本，说明你对“重叠子问题”这个概念已经有感觉了。

5. 常见错误与避坑实录

5.1 输出值和调用次数傻傻分不清

这是阅读程序题最常见的翻车点。题目明明问“输出是什么”，很多人算着算着开始数solve被调用了多少次，最后回答了一个次数。

程序输出的是solve(n)的返回值，不是运行过程信息。这道题的main函数只做了一件事：

cout << solve(n) << endl;

所以你要关注的永远是solve函数的返回值，不是它调用了多少次。如果草稿纸上一堆过程，最终作答前一定要抬头看一眼题目问的到底是输出、调用次数、还是判断某个说法对不对。

5.2 边界条件的顺序不是小事

这道题的第四问已经演示了边界条件顺序的重要性。类似的陷阱还会以其他形式出现，比如把两个边界if写成：

if (n <= 1) return n;

这在很多程序里是等价的，但如果原程序是先判断n == 0再判断n == 1，改成这句就改变了n等于0时的返回值，整个程序行为会变。

我见过不少选手在复盘时抱怨“我明明按代码逻辑算的，怎么错了”，结果一看，第一步就把if顺序记反了。处理递归题，第一件事就是在草稿纸上把判断顺序原样抄一遍，不要凭记忆优化。

5.3 草稿纸上的缩进算术法

手算递归的过程，本质是维护一张“子问题结果表”。我自己的习惯是这样：所有算过的子问题，比如solve(6)=2，solve(7)=3，都集中写在草稿纸左侧，用框框标记，后续用到直接引用。

展开长链的时候，用缩进表达层级关系：

solve(17) solve(8) = 1 solve(9) solve(4) = 1 solve(5) solve(2) = 1 solve(3) = 2 solve(5) = 1 + 2 = 3 solve(9) = 1 + 3 = 4 solve(17) = 1 + 4 = 5

这种缩进写法比画树更清晰，因为它把父子关系用缩进表达，而不是用连线表达。草稿纸看起来清爽，回查也方便。

5.4 选择题的代入排除法

第三问这种选择题，如果时间紧，可以用代入排除法。你已经列出前17项的表，拿选项里的3、4、5、6去查表，会发现n等于7时输出3，n等于9时输出4，n等于17时输出5，而6在表里暂时对应的是n等于11的值。四个选项只有5能和n等于17对上，答案自然锁定。

这个技巧听着简单，但它背后是一个重要的策略：阅读程序的选择题，选项本身就是信息。先看选项，再看题目，很多时候能避免无意义的完整展开。

5.5 考后复盘建议

初赛结束不是终点，把错题真正搞懂才是关键。

我的复盘方法是：把这道题的原程序手动跑一遍，再把递推版代码跑一遍，两者结果对照。如果一致，说明手算基本功没问题，接下来只需要加强速度；如果不一致，就把每一个手算中间值都列出来，和递推数组逐项比对，找到底是哪一个子问题算错了。

这道题很多人算到最后发现，错就错在solve(13)这种中间值上，一步错了后面的全跟着错。找到这一步，比记住整道题答案重要得多。下次遇到类似的递归，你会下意识多检查一遍中间值。

我个人带选手备考时，遇到这种短小的递归题都会强调：不要急着动笔算，先把函数改写成递推式，再决定从哪里入手。这道题如果只记住“输入25输出7”，下次换个n还是不会；但如果记住“奇数分支会分裂成两个相邻子问题”这个结构特征，很多题都能一眼看到底。

最后再分享一个小习惯：考前一周把历年阅读程序题的前两题拿出来，计时10分钟做一遍，不为押题，就为了把“人肉调试”的节奏练稳。初赛拼到最后，往往不是会不会，而是快不快、稳不稳。