Page 122 - 高中 信息技术 选择性必修1 数据与数据结构

第五章 数据结构的应用

出问题的解。
下面以求阶乘数列的函数f(n)为例来描述递归的执行过程。如求f(3)的值，由于3不是
特殊值，因此需要计算3×f(2)；而f(2)又是对它自己的调用，于是再计算f(2)，2也不是特殊

值，需要计算2×f(1)；于是再计算f(1)的值，1是特殊值，于是直接得出f(1)=1，返回上一
步，得出f(2)= 2×f(1)=2，再返回上一步，得出f(3)= 3×f(2)=6，进而得到最终解。求阶乘函
数f(3)的执行过程如图5-3所示。

广东教育出版社

图5-3 求阶乘函数f(3)的执行过程图

3．递归算法的思想与应用
（1）递归算法的思想。

为求解一个不能或不好直接求解的“大问题”，设法将它分解成规模较小但解法相同
的“小问题”，并且这些“小问题”也能采用同样的分解方法再分解成规模更小的“小问
题”，当规模最小的一个或几个值能直接得出解时，再利用这些“小问题”的解构造出
“大问题”的解。

（2）递归算法解决问题的特点。
递归算法有四个特性：
①必须有明确的递归终结条件，否则程序将陷入无穷循环而造成栈溢出。

②子问题在规模上比原问题小，或更接近终止条件。
③子问题可通过再次递归调用求解或因满足终止条件而直接求解。
④子问题的解应能组合为整个问题的解。

（3）递归算法一般用于解决的三类问题。
①数据的定义是按递归定义的。如数学上常用的阶乘数列、斐波那契数列、幂函数
等，它们的定义都是递归的。

②问题方便用递归算法实现。有些问题用递归方法实现更方便，如求阶乘函数的值。
③数据的结构形式是按递归定义的。如链表、树的遍历、图的搜索等。

114 114

21X2204.indd 114 2019/9/26 13:53:38