清华大学电子工程系课件——常用算法设计之二

清华大学电子工程系课件——常用算法设计之二
常用算法设计(2)
孙甲松
清华大学电子工程系
sun@thsp.ee.tsinghua.edu.cn

2007.9.
 5. 递归法
内容要点
(a)递归法是描述算法的一种强有力的方法，
其思想是：将N=n时不能得出解的问题，设
法递归（压栈）将其转化为求n-1,n-2,……
的问题，一直持续到N=0或1的初始情况，由
于初始情况的解可以直接给出或方便得到，
因此开始层层退栈，从而得到N＝2，
3，……，n时的解，得到最终结果。
(b)用递归法写出的程序简单易读，但往往效
率不高，因为每一次的递归函数调用都要压
栈退栈。同时递归次数也不能无限制，因为
每一次的递归函数调用都要压栈占用内存，
而计算机的内存是有限的。
 5. 递归法 (2)
学习难点
递归程序的关键是，对于一个问题，要找出其递归
关系和初始值。方法之一是利用归纳法把一个问题
归纳总结出递归式，加上初始条件，从而编写出递
归函数。
对于单变量的递归问题f(n)，步骤是：
（a）当n＝1或0时，可以得到f(n)的值；
（b）假设小于等于n－1时，都可以得到f(n) 的值；
（ c） 则 对 于 n， 找 出 f(n) 与 f(n-1)，f(n-2)，……
的关系式：f(n)=F(f(n-1)，f(n-2)，……);
（d）开始编写递归程序
 5. 递归法 (3)
【例 1 】编程求解 Hanoi 塔问题：即有 n 个盘
子在 A 处，盘子从大到小，最上面的盘子
最小，现在要把这 n 个盘子从 A 处搬到 C 处，
可以在 B 处暂存，但任何时候不能出现大
的压在小的上面的情况。
 5. 递归