第6周递归第3讲-本周小结数据结构.pdf

《第6周递归第3讲-本周小结数据结构.pdf》由会员分享，可在线阅读，更多相关《第6周递归第3讲-本周小结数据结构.pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1递归基础 递归出口确定递归结束情况确定递归结束情况 递归体确定大小问题的求解情况确定大小问题的求解情况 1/15 对于尾递归，可以用循环递推方法来转换。对于尾递归，可以用循环递推方法来转换。 对于其他递归，可以用栈模拟执行过程来转换。对于其他递归，可以用栈模拟执行过程来转换。 2/15 m(n) = 1当当n=1 m(n) = 2m(n-1)+1当当n1 t(6) = 2t(5) + 1 = 22t(4) + 1 + 2 = 23t(3) + 1 + 2 + 22 = 24t(2) + 1 + 2 + 22+ 23 = 25t(1) + 1 + 2 + 22 + 23+24 = 1 +2 +

2、 22+ 23+24+25= 26- -1=63 3/15 F(1)=1 F(2)=1 F(n)=F(n- -1)+F(n- -2) n2 F(2)F(1) F(3)F(2) F(4) =1=1 =2 =1 =3 求求F(4) = ? 栈 4，? 求出F(4)=3 参数，函数值参数，函数值 3，? 2，? 2，1 1，? 1，1 3，2 2，? 2，1 4，3 4/15 2递归算法设计 利用递归数据结构的递归特性建立递归模型利用递归数据结构的递归特性建立递归模型 编写对应的递归算法编写对应的递归算法 5/15 a1a2an .L f(L)：大问题：大问题 f(L- -next)：小问题：小问题

3、 设计递归算法销毁一个不带头节点的单链表。设计递归算法销毁一个不带头节点的单链表。 f(L) 不做任何事件不做任何事件当当L为空为空 f(L) f(L-next); free(L);当当L非空非空 6/15 void release(LinkList * free(L); 算法如下：算法如下： 7/15 如何将递归特性不明显的问题转化为递归问题求解如何将递归特性不明显的问题转化为递归问题求解 确定问题的形式化描述确定问题的形式化描述 确定哪些是大问题，哪些是小问题确定哪些是大问题，哪些是小问题 确定大、小问题的关系确定大、小问题的关系 确定特殊（递归结束）情况确定特殊（递归结束）情况 8/15

4、 解：解：设设f(a，n，k)为为a0.k（k+1个元素）的所有元素的个元素）的所有元素的全全 排序，为大问题。排序，为大问题。 则则f(a，n，k-1)为为a0.k-1 （k个元素）的所有元素的全排个元素）的所有元素的全排 序，为小问题。序，为小问题。 假设假设a数组含有数组含有1，2，n，求其全排列。，求其全排列。 9/15 假设假设f(a，n，k- -1)可可求，对于求，对于ak位置，可以位置，可以取取a0.k 任何元素值，再任何元素值，再组合组合f(a，n，k-1)，则，则得到得到f(a，n，k) 。 f(a，n，k) 输出输出a当当k=0时时(一个元素的全排列一个元素的全排列) f(

5、a，n，k) ak位置取位置取a0.k任何之任何之值，值，其他其他情况情况 并并组合组合f(a，n，k-1)的结果的结果; 此位置可以取此位置可以取a0ak中任中任 何何值，但值，但不重复不重复！ 采用循环采用循环i：0k，aiak a0 a1 ak-1 ak f(a，n，k- -1) f(a，n，k) 10/15 void perm(int a，int n，int k) int i，j; if (k=0) for (j=0;jn;j+) printf(%d，aj); printf(n); else for (i=0;i=1) printf(n1=%dn,n); /(1) fun(n-1); printf(n2=%dn,n); /(2) n1=3 n1=2 n1=1 n2=1 n2=2 n2=3 fun(3)的的 输出结果输出结果 在在fun(2)的全部功能的全部功能 执行后才执行执行后才执行 fun(3) fun(2) 语句语句(1) 语句语句(2) 掌握递归函数的执行过程有助于递归算法设计 15/15