算法与结构课件第2章递归(华北电力大学科技学院).ppt

一个直接或间接调用自身的算法称为递归算法。 一个使用函数自身给出定义的函数称为递归函数。 q(n,m)= 1 m=1 q(n,n) nm 1+q(n,n-1) n=m q(n,m-1)+q(n-m,m) nm1 0 n1或m1 q(6,6) q(6,5) q(6,4) q(1,5) q(6,3) q(2,4) q(6,2) q(3,3) q(6,1) q(4,2) q(4,1) q(2,2) q(2,1) q(3,2) q(3,1) q(1,2) q(1,1) q(2,2) q(2,1) q(1,1) 1+ + + + + + + = = 1+ 1+ 1+ = 1 1 1 2 3 4 1 1 1 2 3 7 1 2 2 9 1 1 10 11 q(6,1)=1 q(2,1)=1 q(4,1)=1 q(2,2)=2 q(2,1)=1 q(2,4)=2 q(2,2)=2 q(6,4)=9 q(4,2)=3 q(1,1)=1 q(6,2)=4 q(1,5)=1 q(3,1)=1 q(6,5)=10 q(1,1)=1 q(6,6)=11 q(1,2)=1 q(3,2)=2 q(3,3)=3 q(6,3)=7 North China Electric Power University North China Electric Power University §3 递归问题的非递归算法 一般说来，递归过程的实现效率是非常低的，每次递归调 用都必须首先做诸如参数替换、环境保护等事情。造成效率低 下的另一个重要的原因是大量的重复计算。 Fib(5)的计算过程： Fib(0)计算3次； Fib(1)计算5次； Fib(2)计算3次； Fib(3)计算2次； Fib(4)计算1次。 Fib(n)=Fib(n-1)+Fib(n-2) (n1) North China Electric Power University Fib(5) Fib(4) Fib(3) Fib(3) Fib(2) Fib(2) Fib(2) Fib(1) Fib(1) Fib(0) Fib(1) Fib(0) Fib(1) Fib(0) Fib(1) 将递归算法转化成非递归算法的方法： 1)设计迭代算法： 如果一个函数既有递归形式的定义又有非递归的迭代形式 的定义，则可以用循环结构设计出迭代算法。一般说来，如果 在一个函数或过程中只递归调用它 一次，那么它的计算或执行过程可 以看成是线性变化的。 n! (n-1)! (n-2)! · · · 1! 0! 从顶到底递归 从底到顶返回 North China Electric Power University int Fact(int n) { if(n==0) return 1; else return n*Fact(n-1); } int Fact2(int n) { x=1; for(i=1;i=n;i++) x=i*x; return x; } 以Fibnaocci数列为例，看非递归算法的转化 Fib(5) Fib(4) Fib(3) Fib(3) Fib(2) Fib(2) Fib(1) Fib(2) Fib(1) Fib(1) Fib(0) Fib(1) Fib(0) Fib(1) Fib(0) Fib(5) Fib(4) Fib(3) Fib(2) Fib(0) Fib(1) North China Electric Power University int Fib2(int n) { if(n2) return(n); else { int y=0;int x=1;int z; for(int i=2;i=n;i++) { z=y; y=x; x=z+y; } return(x); } } 2)消除尾递归：递归调用是最后一步操作 可以用循环结构通过设置一些工作单元，把递归算法转化为 非递归算法。开始令工作单元等于外层的实际参数，以后随着 循环的执行，不断向里层变化，直到原递归调用的最里层的情 况。循环结束后，执行原属于最里层的操作，而后整个算法结 束。 North China Electric Power University 例:寻找单链表的最后一个结点并打印其数据域的值的过程 search就是一个尾递归过程。 template class Type cl