数据结构与算法--栈和队列2剖析复习过程.ppt

《数据结构与算法--栈和队列2剖析复习过程.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法--栈和队列2剖析一、递归递归是程序设计中最有力的方法之一。优点：采用递归编出的程序简洁、清晰，程序结构符合结构化程序设计，可读性好。问题：编译程序是如何处理这类带有递归调用功能的程序的？如果使用了无递归功能的程序设计语言，应该如何设计和实现这类程序呢？2/39数学中常常利用递归手段来定义一些概念，如求阶乘的运算。n的阶乘定义为：n*(n–1)!n>0n!=1n=0求阶乘3/39递归算法longf(intn){longp;if(n==0)return1;elsereturnn*f(n-1);

2、}voidmain(){longx=f(4);cout<

3、112131415longf(intn){longp;if(n==0)return1;elsereturnn*f(n-1);}n=016171819带回了12122带回了12324带回了627282920带回了225265/39调用前：（1）将所有的实参、返回地址传递给被调用函数保存（2）为被调用函数的局部变量分配存储区（3）将控制转移到被调用函数入口。调用后：（1）保存被调用函数的计算结果。（2）释放被调用函数的数据区（3）依照被调用函数保存的返回地址将控制转移到调用函数函数调用的过程6/39整数划分问题

4、递归法求解排列组合设m.n均为自然数，m可表示为一些不超过n的自然数之和，f(m,n)为这种表示方式的数目。例：f(5,3)=5，5种表示方式：3+23+1+12+2+12+1+1+11+1+1+1+1参看s3/partition.cpp7/39相同的问题:m个苹果放到n个盘子上，问有多少种放法?整数划分问题8/39递归出口：没有苹果或者盘子只剩下1个则只有1种方法整数划分问题5个苹果放到1个盘子里，只有1种放法9/39递归项：(1)苹果数少于盘子数等价于去掉多余的盘子整数划分问题×5个苹果放到6个盘子里的

5、放法，等价于5个苹果放到5个盘子里的放法10/39递归项：(2)苹果数多于盘子数a：至少有1个盘子空着的放法加上b：所有盘子都有苹果的放法整数划分问题a：5个苹果放到4个盘子里，至少有1个盘子空着的放法，就是5个苹果放到3个盘子里的放法11/39递归项：(2)苹果数多于盘子数a：至少有1个盘子空着的放法加上b：所有盘子都有苹果的放法整数划分问题b：既然所有盘子都有苹果，可以把每个盘子里的苹果拿走一个，就是1个苹果放到4个盘子的放法12/39int f(intm,intn){if(m==0

6、

7、n==1)ret

8、urn;//没有苹果或者盘子剩下1个if(m

9、

10、n==1)return1;if(m

11、rnf(m,n-1)+f(m-n,n);}递归实现参考答案参看s3/apple.cpp14/39递归过程f(5,3)=f(5,2)+f(2,3)=f(5,1)+f(3,2)+f(2,3)=1+f(3,1)+f(1,2)+f(2,3)=1+1+f(1,1)+f(2,3)=1+1+1+f(2,2)=1+1+1+1+f(2,1)=1+1+1+1+1=5具体打印形式的输出，请参考partitio.cpp，运用2个栈来输出各种表示方法。15/39分为：(1)在求解过程中直接求值，无需回溯。称这类递归问题为简单递归问题

12、；(2)另一类递归问题在求解过程中不能直接求值，必须进行试探和回溯，称这类递归问题为复杂递归问题求解方法：(1)简单递归问题可以采用递推方法直接求解；(2)复杂递归问题由于要进行回溯，在实现过程中必须借助栈来管理和记忆回溯点。二、递归分类16/39已知勒让德多项式的递归定义如下：1n=0pn(x)=xn=1((2n-1)xpn-1(x)(n-1)pn-2(x))/nn>1简单递归问题例如：求P3(3)