清华大学电子工程系课件——常用算法设计之二常用算法设计(2)孙甲松清华大学电子工程系sun@thsp.ee.tsinghua.edu.cn2007.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.递归