NOIP 提高组初赛 · NOIP 2007 提高组初赛试题 第 20 题

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

别被选项绕晕，核心就盯住两点：FORTRAN77到底禁不禁递归，还有sin(sin(x))到底算不算递归。

很多学生一看到sin(sin(x))就急着选D，其实那是嵌套函数调用，不是递归。递归必须是自己调用自己，而且要有明确的终止条件，否则栈会爆掉。FORTRAN77禁止递归的原因也常被误解，它主要担心的是栈溢出和效率问题，而不是因为递归本身没用。

这道题考查的是对递归算法的理解，包括历史背景、性能特点、编程优势以及递归与嵌套调用的区别。

首先看选项A。FORTRAN77确实禁止了递归。这主要是出于对内存的担忧。递归每调用一次，系统就要在栈上保存一次现场（参数、局部变量、返回地址），如果递归层数很深，栈很快就会溢出。FORTRAN77的设计年代，栈空间相对紧张，所以干脆一刀切禁止。这个说法完全正确。

选项B说递归更快，这显然是错的。递归虽然代码写起来优雅，但每次函数调用都有开销——压栈、跳转、恢复现场。相比之下，非递归通常用循环实现，效率更高。所以解决同一个问题，递归一般比非递归慢，而不是快。

选项C提到复杂问题用递归更容易，这是对的。很多数据结构（比如树、图）和数学问题（比如斐波那契数列、汉诺塔）天然具有递归结构。用递归写代码就像顺着问题的思路走，逻辑清晰，不容易出错。非递归往往需要自己手动维护栈或队列，代码量反而更大。

选项D说sin(sin(x))是递归调用，这是典型的陷阱。递归的定义是：函数在定义中直接或间接地调用自身。sin(sin(x))只是外层函数调用了内层函数，内层函数并没有调用自己，所以这不是递归，而是嵌套调用。真正的递归例子应该是像fact(n) = n * fact(n-1)这样的结构。

总结一下，正确答案是A和C。命题人喜欢在这里挖坑，就是把嵌套调用包装成递归的样子，或者混淆递归的性能特点。解题时务必紧扣递归三要素：有自身调用、有终止条件、有递归公式。只有同时满足这些，才算真正的递归。