NOIP 普及组初赛 · NOIP 2007 普及组初赛试题 第 12 题

近 20 年来，许多计算机专家都大力推崇递归算法，认为它是解决较复杂问题的强有力的工具。在下列关于递归算法的说法中，正确的是（  ）。

这道题考的是递归算法的历史背景与基本概念辨析。拿到题先别急着背定义，想想FORTRAN77那个年代编译器是怎么存局部变量的（静态分配），再区分‘函数嵌套’和‘函数自调’这两个极易混淆的点，就能一眼看出A对D错。

很多学生会误选B，觉得递归优雅所以一定快，其实函数调用有栈开销，递归通常比迭代慢；也有人选C，认为复杂问题递归难写，殊不知像树遍历、分治算法用递归反而逻辑更顺；最典型的坑是D选项，把sin(sin(x))当成递归，其实这是两个独立的函数调用嵌套在一起，递归必须是同一个函数在定义里调用自己，哪怕只调用一次也叫递归。

考点与背景

这道题的核心是考查你对递归算法历史背景和基本概念的掌握程度。在信息学竞赛的初赛里，这种‘历史事实 + 概念辨析’的组合题很常见，命题人往往喜欢用看似合理的描述来迷惑你，比如把‘嵌套调用’包装成‘递归调用’，或者让你对比递归与非递归的性能。

概念梳理（人话版）

递归，简单说就是函数在定义里调用自己。它必须满足两个铁律： 1. 递归调用：函数体内必须有调用自己的语句（哪怕只有一行）。 2. 递归基：必须有终止条件，否则就是死循环。

FORTRAN77 是 1978 年发布的标准，那个年代的编译器为了省事，对局部变量用的是静态分配（stackless）。这意味着局部变量的内存位置在编译时就定死了，不会随函数调用动态变化。如果允许递归，外层调用的局部变量会被内层调用覆盖，数据就乱了，所以标准干脆禁止递归。直到 Fortran 90 引入栈式内存管理，递归才合法。