NOIP 普及组初赛 · NOIP 2018 普及组初赛试题 第 10 题

下面的故事与（ ）算法有着异曲同工之妙。

从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……’”

这题考递归。拿到这种‘故事套故事’的题，别想复杂算法，直接看它是不是‘自己包含自己’，有就是递归，没拆开合并就不是分治。

递归和分治最容易搞混。递归是代码写法（函数自己调自己），分治是解题策略（拆→解→合）。这题纯粹是故事套故事，没拆没合，别被选项D带偏。枚举是穷举所有可能，贪心是每步选最优，这题连‘选’和‘试’的影子都没有，别瞎选。

这题考什么

这道题考查递归这一核心概念，属于算法思想辨析类题目。命题人通过一个极具画面感的‘从前有座山’故事，将抽象的编程概念具象化，要求考生透过现象看本质。在NOIP等竞赛中，这类题目旨在考察学生是否真正理解了算法背后的逻辑结构，而非死记硬背定义。

概念与命题视角

递归的本质非常简单：一个过程在定义中引用了它自己。就像这故事里，老和尚讲的故事内容，又包含了‘讲故事’这个动作本身。在编程世界里，这就对应着函数自己调用自己。

命题人最喜欢在这里挖坑：把递归和分治放在一起。分治（Divide and Conquer）确实也涉及‘自己处理自己’，但它必须包含三个步骤：拆分大问题、解决子问题、合并结果。而这个故事里，老和尚只是不停地讲，没有把山拆成小山，也没有合并，纯粹是无限嵌套。因此，不能因为‘套自己’就选分治，必须看有没有‘拆’和‘合’。