数据结构—栈及递归--含分治及回溯.ppt

3.3 栈与递归 1、什么是递归 2 、为何用递归与递归执行过程 3、如何用递归 显式递归问题，如求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; } 隐式递归—回溯（全部解） 4、递归原理与实现—栈 注意事项： * * 什么是递归？ 为何用递归？ 如何用递归？ 递归实现原理---栈 main函数 { … … 调用函数f … … } f 函数 { … … 调用函数g … … } g 函数 { … … … … … … } f 函数 { … … 调用函数f … … } 递归调用 函数调用 递归指函数直接或间接调用自己 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); } 很多问题能够用递归的方式描述，此时采用递归算法求解直观容易，如求阶乘：F(1)=1; F(n)=n*F(n-1) 3+ 4 * 3+ 3 * 3+ 2 * 6+ 5 * 3+ 1 1 ← 6 ← 2 ← 1 ← 24 ← 120 返址 n r 5 6 7 1 2 3 4 利用递归可方便地解决很多普通方法无法求解的问题 int f ( int n ) { if(n= =1||n= =2) r=1; //写f(n)=1错 else r=f (n-1)+f (n-2);//注意 return r; } 递归求解的关键是找边界条件和递归关系编写递归函数，根据边界条件和递归关系是否明显可将问题分为显示递归和隐式递归两类，前者可直接写出递归函数，后者要通过认真分析找到边界条件，并通过降阶+分治+回溯找递归关系 边界条件 递归公式 Edouard Lucas 1842-1891,French A B C 每次只移一个盘 大盘不能压小盘 类似数学归纳法，假设f(n-1)已知，在此基础上考虑f(n)的求法,如Hannoi塔问题 X Y Z 边界条件: if(n= =1) printf(“%c→%c”,x,z); X Y Z 降阶:假设能把n-1个盘从一个位置移动到另一个位置则... x y z A B C void hanoi(int n, char x, char y, char z) { if(n= =1) printf(“%c→%c\n”,x,z); else { hanoi(n-1, x, z, y);