数据结构-栈和队列 - 中国科学技术大学.ppt

《数据结构-栈和队列 - 中国科学技术大学.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、3.4递归与递归函数1/523.4.1栈定义逻辑特征后进先出(LIFO)进栈出栈an....a1栈顶栈底2/503.4.2栈与递归的实现递归的定义递归(recursion)：直接或间接地调用自身.递归的规则递归终止条件如:n!=(n-1)!*n0!=1递推：从已知的初始条件出发，逐次递推出最后要求的值。如：0!=1,1!=0!*1=12!=1!*2=2……3/503.4.3递归与递推递归intfact1(intn){if(n<0)return-1;elseif(n==0)return1;returnn*fact

2、1(n-1);}递推intfact2(intn){if(n<0)return-1;fact=1;i=1;while(i<=n){fact*=i;i++;}}4/503.4.4栈与递归的实现递归的对象：一个对象部分地包含它自己，或用它自己给自己定义。如某些数据结构的定义线性表的另一种定义(归纳定义):基本步：若元素个数为0，则称为空表归纳步：若元素个数大于0，则有且仅有一个第一个元素(表头)，剩余元素形成一个表(表尾)。递归的过程：一个过程直接或间接地调用自己如：0的阶乘是1，n(n>0)的阶乘等于n乘上(n-1)

3、的阶乘5/503.4.4栈与递归的实现递归的应用递归定义：如阶乘、Fibonacci数列等数据结构：如表、树、二叉树等问题求解：如Hanoi塔6/503.4.5栈与递归的实现–阶乘函数定义是递归的求解阶乘函数的递归算法longfact(longn){if(n==0)return1;//递归结束条件elsereturnn*fact(n-1);//递归的规则}7/503.4.5栈与递归的实现–阶乘函数主程序main():fact(4)参数传递递归调用结果返回回归求值fact(4):fact(3):fact(2):fa

4、ct(1):fact(0):1直接定值为1计算4*fact(3)计算3*fact(2)计算2*fact(1)计算1*fact(0)126248/503.4.6栈与递归的实现–Hanoi塔问题求解是递归的—Hanoi塔voidhanoi(intn,chara,charb,charc)n-圆盘数a-源塔座b-中介塔座c-目标塔座搬动方法n=1,a->cn>1:hanoi(n-1,a,c,b)a->chanoi(n-1,b,a,c)注意用递归调用的结果，不关注该结果如何获得的细节9/50#include

5、dio.h>#includevoidhanoi(intn,chara,charb,charc){if(n==1)printf(“Move%dfrom%cto%c”,n,a,c);else{hanoi(n-1,a,b,c);printf(“Move%dfrom%cto%c”,n,a,c);hanoi(n-1,b,a,c);}}voidmain(intargc,char*argv[]){intn;if(argc==1){printf(“Inputn:”);scanf(“%d”,n);if(n>=1

6、&&n<=20){//限制求解问题的规模。hanoi(n,’A’,’B’,’C’);}else3.4.7栈与递归的实现–递归实现调用函数与被调用函数---系统工作栈执行被调用函数前现场保护：实在参数、返回地址为被调用函数的局部变量分配存储区将控制转移到被调函数的入口从被调用函数返回调用函数前保存被调函数的计算结果释放被调函数的数据区现场恢复：返回11/503.4.7栈与递归的实现–递归实现递归过程与递归工作栈实际的系统中，一般统一处理递归调用和非递归调用递归工作栈活动记录(栈帧stackframe)实在参数、局部

7、变量、上一层的返回地址每进入一层递归，产生一个新的工作记录入栈每退出一层递归，就从栈顶弹出一个工作记录当前执行层的工作记录必是栈顶记录例子：P57hanoi(3,a,b,c)12/503.4.8栈与递归的实现–递归/回溯递归与回溯—N皇后问题回溯是按照某种条件往前试探搜索,若前进中遭到失败,则回过头来另择通路继续搜索.N皇后问题在n行n列的国际象棋棋盘上，若两个皇后位于同一行、同一列或同一对角线上，则称为它们为互相攻击。n皇后问题是指：找到这n个皇后的互不攻击的布局13/503.4.9栈与递归的实现–N皇后问题♛

8、♛♛♛1#主对角线01230123k=i+jk=n+i-j-10#主对角线2#主对角线4#主对角线6#主对角线3#主对角线5#主对角线1#次对角线3#次对角线0#次对角线2#次对角线4#次对角线6#次对角线5#次对角线14/503.4.9栈与递归的实现–N皇后问题基本思路依次为每一行确定该行皇后的合法位置安放第i行皇后时，需要在列的方向从0到n-1试探(j=0,…,n-1