递归算法设计1.ppt

提纲 递归的概念 递归过程 递归程序设计 1.递归的概念 递归算法在可计算性理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。就递归算法而言并不涉及高深数学知识，只不过初学者要建立起递归概念不十分容易。 我们先从一个最简单的例子导入。 1.递归的概念 例：编写一个函数fac，计算阶乘n! 按过去的迭代算法，该函数可以写成： int fac(int n) { int i, p; p = 1; for(i = 2; i = n; i++) p = p * i; return p; } 1.递归的概念 现在换一个角度考虑，n！不仅是1×2×3×…×n, 还可以定义成： 递归的定义： 从程序书写来看，在定义一个函数时，若在函数的功能实现部分又出现对它本身的调用，则称该函数是递归的或递归定义的。 从函数动态运行来看，当调用一个函数A时，在进入函数A且还没有退出（返回）之前，又再一次由于调用A本身而进入函数A，则称之为函数A的递归调用。 1.递归的概念 递归可以分为直接递归和间接递归两种。 直接递归：函数体里面发生对自己的调用； 间接递归：函数A调用函数B，而函数B又直接或间接地调用函数A。 1.递归的概念 不用担心函数A内部又调用函数A，会使得调用无休无止，肯定存在某个条件，当该条件成立的时候，函数A将不会再调用自身。 例如，求n！时，该结束条件是 if(n == 0) int f(int n) { if(n == 0) return 1; else return n * f(n-1); } 提纲 递归的概念 递归过程 递归程序设计 2.递归过程 求f（2）的 递归调用过程？ 2.递归过程 2.递归过程 请思考： 发出f(2)调用时，将2赋值给形参n。然后发出f(1)调用，将1赋值给形参n。接着发出f(0)调用，将0赋值给形参n。后来赋给形参n的值会不会覆盖原来赋给n的值（如值1覆盖原来的值2）？为什么？ －不会，每一次函数调用会在栈顶分配新的活动记录。 对递归函数的每一次调用结束返回时，为何能回到调用前的程序运行状态？如f(1)调用结束返回f(2)时，n的值为2。 －函数访问的永远是栈顶的活动记录。当f(1)调用结束时，位于栈顶的f(1)的活动记录将出栈，此时位于栈顶的将是f(2)的函数活动记录。 2.递归过程 求f(6)的递归调用过程 2.递归过程 可见，递归算法的执行过程分递推和回归两个阶段。当递推时，并没有求值的计算操作，实际的计算操作是在回归过程实现的。 递推阶段： 递推阶段是个不断简化问题的阶段：把对较复杂问题（规模为n）的求解转化为比原问题简单一些的问题（规模小于n）的求解 。例如对f (6)的求解转化为f(5)的求解， 对f(5)的求解转化为f(4)的求解…直到转化为对f(0)的求解。 当递推到最简单的不用再简化的问题时，递推终止。如f函数中，n==0的情况。 就象剥一颗圆白菜，从外向里，一层层剥下来，到了菜心，就不再继续剥了。 2.递归过程 回归阶段： 在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解 。如在得到f(1)的解后，又依次得到f(2)、f(3)…直到f(6)的值。 就像将剥下来的白菜叶又从里往外一叶一叶合起来，直到最外层菜叶。 2.递归过程 思考：递归与迭代的比较(以求阶乘为例)。 迭代:从已知的初始条件出发，逐次去求所需要的阶乘值，这相当于从菜心“推到”（通过循环）最外层的菜叶。 f(0) = 1 f (1) = 1*f (0) = 1 f (2) = 2*f (1) = 2 递归：先从最外层的菜叶“递推”到菜心(递归函数调用)，再从菜心“回归”到最外面的菜叶（递归函数返回）。 2.递归过程 递归算法的出发点不放在初始条件上，而放在求解的目标上，是从所求的未知项出发逐次调用本身的求解过程，直到递归的边界（即初始条件）。 就求阶乘而言，读者会认为递归算法可能是多余的，费力而不讨好。但许多实际问题不可能或不容易找到显而易见的迭代关系，这时递归算法就表现出了明显的优越性。 下面我们将会看到，递归算法比较符合人的思维方式，逻辑性强，可将问题描述得简单扼要，具有良好的可读性，易于理解，许多看来相当复杂，或难以下手的问题，如果能够使用递归算法就会使问题变得易于处理。 提纲 递归的概念 递归过程 递归程序设计 3.递归程序设计 什么样的问题可以用递归解决？ 如果解决问题的方法是把该问题分解成小的子问题，并且这些小的子问题可以用同样的算法解决，这样不断分解，直