NOIP 普及组初赛 · NOIP 2013 普及组初赛试题 第 3 题

下面的故事与（ ）算法有着异曲同工之妙。 从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……’”

这题考递归。看到‘故事套故事’，马上想到函数自己调用自己。别被枚举、贪心、分治带偏，关键是抓住‘自指’这个特征。

学生容易把递归和分治搞混，分治是‘分→治→合’三步，这题只有‘自指’没有分解合并，别选D。枚举是暴力穷举，贪心是局部最优，都跟题意无关。

这道题考什么

故事里‘故事套故事’，本质是自己调用自己，对应算法就是递归。

概念：递归是什么

递归就是函数（或过程）在定义中直接或间接地调用自身。每次调用时，问题规模会变小（比如从n变成n-1），直到达到基准情况（不再调用自身）为止。递归的核心有两点： 1. 自指——函数调用自己； 2. 终止条件——避免无限循环。