《第一章算法.ppt

#include iostream.h void main() { int u, n ; u=1; for (n=9; n=1; n--) u = (u+1)*2 ; cout原来的桃子数：uendl ; } Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 递归 处理重复性的操作，有两种方法：一种用循环实现；另一种用递归实现。在函数体中直接或间接调用自己，这种函数是递归的。人们通常使用直接递归，很少用间接递归，所以下面介绍的内容都是直接递归。 直接递归 sum() { … sum(); … } 从图上看，递归是无休止的自身调用，构成循环。但实际情况中不应该这样。不能出现无休止的循环调用。函数sum中的实参一定要有变化，程序中一定要有使递归终止的判断语句，有限次调用后能够停止递归调用。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 一个问题要用递归的方法解决，必须满足3个条件 ⑴ 要解决的问题可转换为一个新问题，而这个新问题的解法与原来问题的解法相同，只是所处理的对象有规律变化，递增或递减； ⑵ 可以应用这个转换过程使问题得到解决； ⑶ 要有一个明确的递归结束条件（称为递归边界）； 这三条或归结为一个递归公式，或归结为一个递归算法（指非公式表达，如汉诺塔） 递归模型 一般地，一个递归模型是由递归出口和递归体两部分组成，前者确定递归到何时终止，后者确定递归的方式。其数学模型可描述为： 递归出口： S0与M0均为常数（递归调用终止） 递归体一般形式： 这里的Sn是一个递归“大问题”，S1, S2,…, Sn-1为递归“小问题”，C1, C2,…, Cn-1是可以直接（用非递归方法）解决的问题，g是一个非递归函数。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 递归的执行过程 实际上，递归是把一个不能或不好直接求解的“大问题”转化成一个或几个“小问题”来解决，再把这些“小问题”进一步分解成更小的“小问题”来解决；如此分解，直至每个“小问题”都可以直接解决（此时分解到递归出口），一旦遇到递归出口，分解过程结束，开始回推过程，回推过程是从一个已知值推出下一个值，实际上这是一个递推过程。 可见，递归的执行过程由分解和回推两部分构成，要经历许多步才能求出最后的值。 递归的分解是“量变”过程，即“大问题”在慢慢变小，但尚未解决，遇到递归出口，便发生“质变”，即原递归问题转化为递推问题。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 递归程序阅读 递归程序的执行过程实际上是一种函数嵌套调用，只是反复调用的是自身。同一个函数每次被调用时，都会在栈中分配一段独立的栈空间，用以存放本次函数调用时的形参值、局部变量和返回地址。即每次函数递归调用时，其形参和局部变量都是独立的。所以，阅读递归程序时需把握“当前”这一概念，不同层次上的形参虽然同名，但指代不同的内存空间，表示的含义（即形参的值）当然也就不相同。 例1、求 递归体： ；递归出口： Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 递归程序执行过程（不同递归层次的调用中形参n的值不同；return返回的值也不同） #include iostream.h double p(int x, int n) { double f ; if(n==1) f = x; else f = x*p(x,