趣谈数据结构(五)
在趣谈数据结构(四)中,我们了解了迭代与递推。与迭代、递推相对应的算法为递
归,本趣谈数据结构,我们就来谈一谈递归算法。
递归算法作为计算机程序设计中的一种重要的算法,是较难理解的算法之一。简单地
说,递归就是编写这样的一个特殊的过程,该过程体中有一个语句用于调用过程自身(称
为递归调用)。递归过程由于实现了自我的嵌套执行,使这种过程的执行变得复杂起来,
其执行的流程可以用图 1 所示。
图 1 递归过程的执行流程
从图 可以看出,递归过程的执行总是一个过程体未执行完,
就带着本次执行的结果又进入另一轮过程体的执行,……,如此
反复,不断深入,直到某次过程的执行遇到终止递归调用的条件
成立时,则不再深入,而执行本次的过程体余下的部分,然后又
返回到上一次调用的过程体中,执行其余下的部分,……,如此
反复,直到回到起始位置上,才最终结束整个递归过程的执行,
得到相应的执行结果。递归过程的程序设计的核心就是参照这种
执行流程,设计出一种适合逐步深入,而后又逐步返回的递归
调用模型,以解决实际问题。
利用递归调用程序设计技术可以解决很复杂但规律性很强的
问题,并且可以使程序变得十分简短。
例 1 利用递归调用手段编程计算 N!。
分析:根椐数学知识,,正整数 的阶乘为:
, 该阶乘序列可转换为求 ,而
以可转换为,……,直至转换为 ,而 。
源程序如下