栈与递归含分治与回溯.PPTVIP

3.3 栈与递归 1、什么是递归 2、递归原理与实现—栈 3 、为何用递归与递归执行过程 4、如何用递归 显式递归问题，如求Fibnacci数列 F(n)=F(n-1)+F(n-2)递归公式；F(1)=1,F(2)=1边界条件 隐式递归—降阶 hanoi(n, x, y, z); 降阶：分三步 hanoi(n-1, x, z, y); printf(“%c→%c”,x,z); hanoi(n-1, y, x, z); 递归函数： hanoi(int n, char x,char y, char z) 基始条件: if(n= =1) printf(“%c→%c”,x,z); 降阶：分三步 hanoi(n-1, x, z, y); printf(“%c→%c”,x,z); hanoi(n-1, y, x, z); 注意事项： 隐式递归—分治 --树的相关操作 隐式递归—回溯 --8皇后问题 void PrintChessBoard(int a[N][N]) { int i,j; for(i=0;iN;i++) { for(j=0;jN;j++) { printf(%3d,a[i][j]); } printf(\n); } printf(\n\n); } int Verify(int a[N][N],int i) { int sum,j,k; for(j=0;jN;j++) //逐列检查 { sum=0; for(k=0;k=i;k++) //看当前列前i行中是否冲突 { sum+=a[k][j]; } if(sum1)return 0; } return 1; } 隐式递归—回溯（全部解） 注意事项： * * 什么是递归？ 为何用递归？ 如何用递归？ 递归实现原理---栈 main函数 { … … 调用函数f … … } f 函数 { … … 调用函数g … … } g 函数 { … … … … … … } f 函数 { … … 调用函数f … … } 递归调用 函数调用 递归指函数直接或间接调用自己 系统在函数调用前完成的工作： 将返回地址等信息入栈，并保存本层局部变量值 为被调函数的局部变量分配存储区 将控制转移到被调函数代码区的入口 系统在被调函数返回之前完成的工作： 保存被调函数的计算结果 释放被调函数的数据区 出栈并根据返回地址将控制转移到调用函数,恢复执行 递归作为函数调用特例过程同上，允许递归的语言中系统自动维护一个递归工作栈,不支持递归时用户可仿照系统自行设立递归工作栈 int f ( int n ) { 1 int r; 2 if(n= =1) r=1; 3 else r=n*f (n-1); 4 return r; } void main( ) { 5 int x; 6 x=f(5); 7 print(x); } 3+ 4 * 3+ 3 * 3+ 2 * 6+ 5 * 3+ 1 1 ← 6 ← 2 ← 1 ← 24 120 返址 n r 利用栈将递归化为非递归举例： int f(int n ){ SElemType e,temp; SqStack S; InitStack(S); while(n1){ //递归前进，入栈 e.n=n; Push(S,e); n--; } e.n=1;e.r=1; //边界条件 while(!StackEmpty(S)){ //递归后退，出栈 Pop(S,temp); temp.r=temp.n*e.r; e=temp; }//递归结束 return e.r;//返回结果 }//更多可参考相关论文 int f ( int n ) { int r; if(n= =1) r=1; else r=n*f (n-1); return r; } void main( ) { int x; x=f(5); printf(“%d”,x); } 很多问题能