《数据结构递归算法》由会员分享，可在线阅读，更多相关《数据结构递归算法（12页珍藏版）》请在金锄头文库上搜索。
1、周四交作业1递 归 算 法2华中科技大学计算机学院1。递归算法思想：在以一种方法求解问题时，将复杂的问题分解成相对 简单的子问题，而在求解子问题时，使用同样的方法进行 。求解 规模为n的问题分 解1.特殊情况的求解：（如：n=1,n=2等）2.分解成子问题：3.求解规模为n的问题求解规模为 n-1的问题求解规模为 n-2的问题3华中科技大学计算机学院2. 递归函数的概念。间接递归调用：int f1() f2()void f2() x=f1();直接递归调用：long FiBo(int n) long f1,f2;if (n=1 |n=2) return 1;f1=FiBo(n-1);f2=Fi
2、Bo(n-2);return f1+f2;4华中科技大学计算机学院3。递归函数的定义：例: 计算n的阶乘的算法:1 n=0 特殊情况的求解n!=n*(n-1)! n0long fac(int n) if (n=0) return 1; /*特殊情况处理、递归出口*/return n*fac(n-1); /*最后的求解*/5华中科技大学计算机学院例: 求a，b的最大公约数的算法:a b=0 特殊情况的求解gcd(a,b)=gcd(b,a%b) 其他 int gcd(int a，int b)if (b=0) return a; /*特殊情况的处理*/return gcd(b,a%b); /*最后的
3、求解*/6华中科技大学计算机学院例: 求Fibonacci级数第n项的算法:1 1 2 3 5 8 13 211 n=1,2 特殊情况的求解Fibo(n)=Fibo(n-1)+Fibo(n-2) n2 long FiBo(int n)long f1,f2;if (n=1 |n=2) return 1;f1=FiBo(n-1);f2=FiBo(n-2);return f1+f2;7华中科技大学计算机学院4。递归函数的执行过程：main() printf(“%ld”,fac(3);fac(3)变变量存储储分配 :n: 3f: ? if (n=0)return 1; f=fac(n-1);retur
4、n n*f; 变变量存储储分配 :n: 2f: ? if (n=0)return 1; f=fac(n-1);return n*f; 变变量存储储分配 :n: 1f: ? if (n=0)return 1; f=fac(n-1);return n*f; 变变量存储储分配 :n: 0f: ? if (n=0)return 1; f=fac(n-1);return n*f; 各个n、f 分 配不同存储 单元8华中科技大学计算机学院fac(3)变变量存储储分配 :n: 3f: ? if (n=0)return 1; f=fac(n-1);return n*f; 变变量存储储分配 :n: 2f: ?
5、if (n=0)return 1; f=fac(n-1);return n*f; 变变量存储储分配 :n: 1f: ? if (n=0)return 1; f=fac(n-1);return n*f; 变变量存储储分配 :n: 0f: ? if (n=0)return 1; f=fac(n-1);return n*f; fac(3)变变量存储储分配 :n: 3f: ? if (n=0)return 1; f=fac(n-1);return n*f; 变变量存储储分配 :n: 2f: ? if (n=0)return 1; f=fac(n-1);return n*f; 变变量存储储分配 :n:
6、1f: 1 if (n=0)return 1; f=fac(n-1);return n*f; 回归 过程 ：11!9华中科技大学计算机学院fac(3)变变量存储储分配 :n: 3f: ? if (n=0)return 1; f=fac(n-1);return n*f; 变变量存储储分配 :n: 2f: 1 if (n=0)return 1; f=fac(n-1);return n*f; 回归过程 ：2!fac(3)变变量存储储分配 :n: 3f: 2 if (n=0)return 1; f=fac(n-1);return n*f; 3!10华中科技大学计算机学院5。求递归函数时间复杂度：例：用
7、二分法查找int binary(int a, int l,int h, int x)/a中al,al+1.ah递增排列int m;if (lh) return -1; /*数据元素个数为0*/m=(l+h)/2;if (am=x) return mif (amx) return binary(a,l,m-1,x);else return binary(a,m+1,h,x);11华中科技大学计算机学院C1 n=0 C1为常数f(n)=f(n/2)+C2 n0 C2为常数存在k(k=0)，使 2k-1=n2k 不妨假设n=2kf(n)=f(2k-1)+C2= f(2k-2)+2C2= f(1)+kC2=f(0)+(k+1)C2=C1+(k+1)C2T(n)=O(f(n)=O(C1+(k+1)C2)=O(k)=O(log2n) =O(logn)12
