NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 3 题

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

看到‘从前有座山…山里有座庙…庙里有个老和尚给小和尚讲故事：从前有座山…’，立刻抓住‘嵌套讲自身’这个特征，直接对应算法中的自调用——递归。

学生容易把递归和分治搞混，觉得都是‘把大问题拆小’。其实分治是‘先分后合’，把原问题切成若干互不重叠的子问题，各自解决后再合并结果；而递归的核心是‘自指’，函数直接或间接调用自己，用同样的逻辑处理规模更小的同类问题。这道题的故事里，老和尚讲的故事内容里又包含了老和尚讲的故事，没有‘分解’成不同部分，只是不断往里套，所以不是分治。

这道题考什么

考的是对算法思想本质的理解，尤其是递归与分治、贪心、枚举这些常见算法的区别。命题人最爱用生活化的小故事来包装抽象概念，让你从描述中识别出算法特征。

概念：递归是啥？

递归（Recursion）就是函数直接或间接调用自身。它有两个必备条件： 1. 递归表达式：把原问题转成规模更小的同类问题； 2. 递归边界：最小规模问题的直接解，防止无限循环。