递归算法 15p.pptVIP

递归算法 递归的定义 这个流程如下: void B( ) { ….. } void A( ) { ….. B( ); ….. } void main( ) { ….. A( ); ….. } main函数 A函数 B函数 调用A函数 调用B函数 结束 递归的定义 若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的 若一个函数直接地或间接地调用自己，则称这个函数是递归函数(recursive function) 在以下三种情况下，常常用到递归方法 定义是递归的 数据结构是递归的 问题的解法是递归的 递归函数分为直接递归与间接递归 直接递归：在函数中出现调用函数本身 间接递归：在函数中调用了其它函数，而该其 它函数又调用了本函数 两种不同的递归程序图示如下： 递归设计方法 递归设计首先要确定求解问题的递归模型，了解递归的执行过程，在此基础上进行递归程序设计 递归模型 递归模型反映一个递归问题的递归结构，例如 f(1)=1 f(n)=n*f(n-1) n1 第一个式子给出了递归的终止条件，第二个式子给出了f(n)的值与f(n-1)的值之间的关系，我们把第一个式子称为递归出口，把第二个式子称为递归体。 一般地，一个递归模型是由递归出口和递归体两部分组成，前者确定到何时为止，后者确定递归的方式。 实际上，递归是把一个不能或者不好直接求解的大问题转化为一个或者几个小问题来解决，如此分解，直至每个小问题都可以直接解决（此时分解到递归出口） 注意：递归分解不是随意的分解，递归分解要保证大问题与小问题相似，即求解过程与环境相似。 求解f(n)的分解过程如下 f(n) - f(n-1) - f(n-2) …… f(3) - f(2) - f(1) 一旦遇到递归出口，分解过程结束，开始求值过程，所以分解过程是量变，即原来的大问题在慢慢变小，但尚未解决，遇到递归出口后，便发生了质变，即原递归问题转化为直接问题。 上面的求值过程如下： f(n) - f(n-1) - f(n-2) - f(n-3) …… - f(2) - f(1) 这样f(n)就计算出来了，因此，递归的执行过程由分解和求值两部分构成。 由上面的分析可以得出一般的递归设计的步骤如下 (1) 对原问题f(s)进行分析，假设出合理的较小问题f(s’) (2) 假设f(s’)是可解得，在此基础上确定f(s)的解，即给出f(s)与f(s’)的关系 (3) 确定一个特定情况(如f(1)或f(0))的解，由此作为递归出口 递归与循环 递归与循环的相似点 递归程序和循环有一些相似之处，递归程序在调用自己的时候会不断的调用自己,所以肯定有一个判断控制语句,这一个点与循环控制语句相同,因为循环也是有一个判断语句,否者两者都会出现问题，递归会出现无限递归而循环也会出现无限循环。因此递归程序具有循环的功能,所以用循环写的代码可以用递归写的代码代替。 假如字符数组a中存储有一字符串“12345”， 现在需要输出: 5 4 3 2 1 因为递归可以通过系统自动调用堆栈，所以可以这样写: 递归函数示例 阶乘 汉诺塔 递归函数示例——阶乘 用循环实现阶乘计算的函数 long fac(int n) { long s; int i; for(s = 1, i = 1; i = n; i++)  s *= i; return s; } 递归函数示例——汉诺塔 汉诺塔问题的目标是把所有的圆盘从最初的第一根柱子移动到最终的那个柱子上。我们利用中间那个柱子作为临时放置圆盘的地方，但必须遵守如下3条规则。 ● 一次只能移动一张圆盘 ●不能将较大圆盘放在较小的圆盘上方 ●除了那张在柱子之间搬动的圆盘之外，所有圆盘都必须放在某根柱子上 假设我们只有三张圆盘，为了将这所有这三张圆盘从第一根柱子移到第三根，首先必须做到——较小的两张圆盘都不再挡道（处在第二根柱子上），这样最大的那张圆盘才能从第一根柱子移到第三根柱子。 下面根据这种思想形成一般性的策略。要将一叠圆盘（N个）从最初的柱子移到最终的柱子： ● 将最上方的N