递归算法课件.ppt

《递归算法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、例如我们把刚才讲故事的过程包装成一个函数，就会得到：voidStory(){System.out.print(“从前有座山，山里有座庙，庙里有个老和尚，老和尚在讲故事，它讲的故事是：”);Story();}函数的功能是输出这个故事的内容，当我们运行程序后，重复的输出这段内容。我们发现由于每个故事都是相同的，所以出现导致死循环的迂回逻辑，故事将不停的讲下去。出现死循环的程序是一个不健全的程序，我们希望程序在满足某种条件以后能够停下来正如我们听了几遍相同的故事后会大叫：“够了！”。这个“够了”就是这个程序的出口，于是我们可以得到下面的程序：publicclass和尚

2、讲故事{staticintmax=4;publicstaticvoidmain(String[]args){Story(1);}privatestaticvoidStory(intn){if(n<=max){System.out.print("从前有座山，上里有座庙，庙里有个老和尚在讲故事，讲的故事是：");n++;Story(n);}else{System.out.println("都讲了N便了，你烦不烦啊！");}}}在下面二种情况中存在算法调用自己的情况：若一个算法直接的或间接的调用自己本身，则称这个算法是递归算法。（1）问题的定义是递推的阶乘函

3、数的常见定义是：递归的概念也可定义为：写成函数形式，则为：这种函数定义的方法是用阶乘函数自己本身定义了阶乘函数，称上式为阶乘函数的递推定义式。数学归纳法表明，如果我们知道某个论点对最小的情形成立，并且可以证明一个情形暗示着另一个情形，那么我们就知道该论点对所有情形都成立。数学有时是按递归方式定义的。例1：假设S（n）是前n个整数的和，那么S（1）=1，并且我们可以将S（n）写成S（n）=S（n-1）+n。根据递归公式，我们可以得到对应的递归函数：intS(intn){if(n==1)return1;elsereturnS(n-1)+n;}函数由递归公式得

4、到，应该是好理解的，要想求出S（n），得先求出S(n-1)，递归终止的条件（递归出口）是(n==1)。例2：斐波那契数列为：1、1、2、3、5、8、13、21、…，即fib(1)=1;fib(2)=1;fib(n)=fib(n-1)+fib(n-2) (当n>2时)。我们曾经用迭代法解决了这个问题，实际上数列公式本身是一个递归公式，如果用递归算法来解将更自然。根据递归公式，很容易递归函数：intFib(intn){if(n<1)return0;if(n==1

5、

6、n==2)//递归出口return1;returnFib(n-1)+Fib(n-2);}求Fib(

7、5)的递归计算过程如图所示。Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1)Fib(0)Fib(2)Fib(1)Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)斐波那契数列Fib(5)的递归调用树为了计算Fib(5)，需要先计算Fib(4)和Fib(3)；而计算Fib(4)又需要计算Fib(3)（再一次计算）和Fib(2)，…….由上图可知，为了计算Fib(5)，需要计算1次Fib(4)，2次Fib(3)，3次Fib(2)，5次Fib(1)，3次Fib(0).加上Fib(5)1次，所有的递归调用次数达到15次。（图中15个点表示

8、15次运算）更一般地，设Fib(n)需要总的递归调用次数为NumCall(n)，那么NumCall(n)等于多少？并不是每个问题都适宜于用递归算法求解。适宜于用递归算法求解的问题的充分必要条件是：（1）问题具有某种可借用的类同自身的子问题描述的性质；（2）某一有限步的子问题（也称作本原问题）有直接的解存在。如何设计递归算法？由于许多问题并不是很明显的表现出递归的关系，所有很大一部分需要我们进行推导，从而得出递归关系，有了递归关系，编写代码就相对的比较简单了。首先,我们了解递归算法的特点，所谓的递归，就是把一个不能或不好直接求解的“大问题”转化成一个或几个与原问题相似的“小问

9、题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决，如此分解，直至每个“小问题”都可以直接解决。在逐步求解“小问题”后，再返回得到“大问题”的解。因此，递归的执行过程由分解和求值两部分构成。首先是逐步把“大问题”分解成形式相同但规模减小的“小问题”，直至分解到递归出口。一旦遇到递归出口，分解过程结束。然后，开始求值过程，所以分解过程是“量变”过程，即原来的“”大问题”在慢慢变小，但尚未解决。遇到递归出口后，便发生了“质变”，即原递归问题转换成直接问题。由于递归只需要少量的步骤就可描述解