递归与深度优先搜索算法

1、第3讲 递归与深度优先搜索算法2014年 赵宗昌一一. 递归递归2014年 赵宗昌2014年 赵宗昌从前有座山山上有座庙,庙里有个老和尚,老和尚在给小和尚讲故事: 从前有座山山上有座庙,庙里有个老和尚,老和尚在给小和尚讲故事:从前有座山山上有座庙,庙里有个老和尚,老和尚在给小和尚讲故事:从前有座山山上有座庙,庙里有个老和尚,老和尚在给小和尚讲故事: 这就是递归2014年 赵宗昌递归的概念：递归的概念： 一个过程一个过程(或函数或函数)直接或间接调用自己直接或间接调用自己本身本身,这种过程这种过程(或函数或函数)叫递归过程叫递归过程(或函数或函数). 满足某个条件后递归终止满足某个条件后递归终止

2、。2014年 赵宗昌递归的关键：递归的关键：1.确定递归公式（关系）确定递归公式（关系）2.确定边界确定边界(终止终止)条件条件当递归没有到达边界终止时，继续向前，直至边界才返回。当递归没有到达边界终止时，继续向前，直至边界才返回。2014年 赵宗昌Function 函数名（参数）：类型；Procedure 过程名（）参数；Int 函数名（参数）；Void 函数名（参数）；2014年 赵宗昌过程过程过程过程过程过程过程过程递递归归结结束束2014年 赵宗昌小猴摘了很多桃子。小猴摘了很多桃子。第一天吃了一半又多吃一个；第一天吃了一半又多吃一个；第二天又吃掉剩下的一半再多吃一个；第二天又吃掉剩下的

3、一半再多吃一个；以后每天都是吃前一天剩下的一半再多一个。以后每天都是吃前一天剩下的一半再多一个。如此下去，到第十天恰好还剩一个桃子。如此下去，到第十天恰好还剩一个桃子。问第一天小猴摘了多少桃子？问第一天小猴摘了多少桃子？【例例1】猴子吃桃问题猴子吃桃问题2014年 赵宗昌u关系：第第i天的桃子天的桃子=(第第i+1天的桃子天的桃子 +1)*2i=10时时 ，有，有1只桃子。只桃子。f(10)=1f(i)=2*(f(i+1)+1)求 f(1)=?2014年 赵宗昌u方法1： varvar n:longint; n:longint; function f(i:longint):longint; f

4、unction f(i:longint):longint; begin begin if i=10 then f:=1 if i=10 then f:=1 else f:=(f(i+1)+1) else f:=(f(i+1)+1)* *2;2; end; end; beginbegin n:=f(1); n:=f(1); writeln(n); writeln(n); end.end.2014年 赵宗昌u方法1： varvar n:longint; n:longint; function f(i:longint):longint; function f(i:longint):longint;

5、begin begin if i=10 then if i=10 then exitexit(1);(1); exitexit(f(i+1)+1)(f(i+1)+1)* *2);2); end; end; beginbegin n:=f(1); n:=f(1); writeln(n); writeln(n); end.end.2014年 赵宗昌# include # include # include # include using namespace std;using namespace std;int int (int i)(int i)if (i=10) return 1;if (i=

6、10) return 1;return 2return 2* *(f(i+1)+1);(f(i+1)+1); int main()int main() coutf(1); cout1n1时时递归的执行过程2014年 赵宗昌varvar n:integer; n:integer; function f(i:integer):integer; function f(i:integer):integer; begin begin if i=1 then f:=1 if i=1 then f:=1 else f:=i else f:=i* *f (i-1);f (i-1); end; end; beg

7、in begin readln(n); readln(n); writeln(f(n); writeln(f(n); end. end.2014年 赵宗昌varvar n:integer; n:integer; function f (i:integer):integer; function f (i:integer):integer; begin begin if i=1 then if i=1 then exitexit(1);(1); exitexit(i(i* *f (i-1);f (i-1); end; end; begin begin readln(n); readln(n); w

8、riteln(f (n); writeln(f (n); end. end.2014年 赵宗昌【例【例3】求最大公约数】求最大公约数输入输入a和和b，输出，输出a和和b的最大公约数。的最大公约数。如：如：输入：输入：100 75输出：输出：252014年 赵宗昌u欧几里德算法（又称辗转相除法）用于计算两个正整数用于计算两个正整数a a，b b的最大公约数。的最大公约数。一般把一般把a a和和b b的最大公约数记为的最大公约数记为gcd(a,b)gcd(a,b)。公式：公式：gcd(a,b)=gcd(b,a mod b)gcd(a,b)=gcd(b,a mod b)gcd(a,0)=agcd(a

9、,0)=a如：如：gcd(100,75)=gcd(75,25)=gcd(25,0)=25gcd(100,75)=gcd(75,25)=gcd(25,0)=25；2014年 赵宗昌【方法【方法1 1】varvar a,b,r:longint; a,b,r:longint;beginbegin readln(a,b); readln(a,b); while b0 do while b0 do begin begin r:=a mod b; r:=a mod b; a:=b; a:=b; b:=r; b:=r; end; end; writeln(a); writeln(a);end.end.201

10、4年 赵宗昌u【方法2】递归varvar a,b:longint; a,b:longint; function gcd(a,b:longint):longint; function gcd(a,b:longint):longint; begin begin if b=0 then exit(a); if b=0 then exit(a); exit(gcd(b,a mod b); exit(gcd(b,a mod b); end; end;beginbegin readln(a,b); readln(a,b); writeln(gcd(a,b); writeln(gcd(a,b);end.en

11、d.2014年 赵宗昌varvar n:longint; n:longint; procedure f(n:longint); procedure f(n:longint); begin begin if n0 then if n0 then begin begin f(n div 2); f(n div 2); write(n mod 2); write(n mod 2); end; end; end; end;beginbegin readln(n); readln(n); f(n); f(n);End.End.# include # include using namespace std

12、;void dfs(int i)if (i0) dfs(i/2); printf(%d,i % 2);int main() int n; scanf(%d,&n); ; return 0;n=204.4.读程序写结果读程序写结果2014年 赵宗昌varvar n:longint; n:longint; procedure dfs(i:longint); procedure dfs(i:longint); begin begin writeln(i); writeln(i); dfs(i+1); dfs(i+1); end; end;beginbegin dfs(1); dfs(1);e

13、nd.end.# include # include # include # include using namespace std;using namespace std;void void (int i)(int i)printf(%dn,i);printf(%dn,i); dfs(i+1); dfs(i+1); int main()int main() ; ; return 0; return 0; 5.5.递归的层数递归的层数2014年 赵宗昌问题的提出：问题的提出： Hanoi塔由塔由n个大小不同的圆盘和个大小不同的圆盘和3根木柱根木柱1,2,3组成。开始时，这组成。开始时，这n个个

14、圆盘由大到小依次套在圆盘由大到小依次套在1柱上，如图所示。柱上，如图所示。现在要求用最少的移动次数把现在要求用最少的移动次数把1柱上柱上n个圆盘按下述规则移到个圆盘按下述规则移到3柱上：柱上：(1) 一次只能移一个圆盘；一次只能移一个圆盘；(2) 圆盘只能在圆盘只能在3个柱上存放；个柱上存放；(3) 在移动过程中，不允许大盘压小盘。在移动过程中，不允许大盘压小盘。请编程描述移动的过程。请编程描述移动的过程。 。6 Hanoi（汉诺塔）问题（汉诺塔）问题2014年 赵宗昌1 : 1-31 : 1-22 : 1-31 : 2-31 : 1-32 : 1-21 : 3-23 : 1-31 : 2-1

15、2 : 2-31 : 1-31 : 1-22 : 1-31 : 2-33 : 1-21 : 3-12 : 3-21 : 1-24 : 1-31 : 2-32 : 2-11 : 3-13 : 2-31 : 1-22 : 1-31 : 2-3N=4N=3N=2N=12014年 赵宗昌第一步：先借助第一步：先借助3柱把柱把1柱上面的柱上面的n-1个盘子移动到个盘子移动到2柱上。柱上。第二步：然后再把第二步：然后再把1柱最下面的一个盘子移动到柱最下面的一个盘子移动到3柱上。柱上。第三步：再借助第三步：再借助1柱把柱把2柱上的柱上的n-1个盘子移动到个盘子移动到3上。上。2014年 赵宗昌procedu

16、re move(i,x,y,z:integer);procedure move(i,x,y,z:integer); / /把把x x柱上的编号柱上的编号1 1到到i i的的i i个盘子借助个盘子借助y y移动到移动到z z上上 beginbegin if i=1 then writeln(1, : ,x,-,z) if i=1 then writeln(1, : ,x,-,z) else else begin begin move(i-1,x,z,y); move(i-1,x,z,y); writeln(i, : ,x,-,z); writeln(i, : ,x,-,z); move(i-1,

17、y,x,z); move(i-1,y,x,z); end; end; end; end;readln(n);move(n,1,2,3);2014年 赵宗昌 # include # include # include # include using namespace std;using namespace std; void move(int i,int a,int b,int c)void move(int i,int a,int b,int c)if (i0) if (i0) move(i-1,a,c,b);move(i-1,a,c,b);printf(%d : %d - %dn,i,a,c);printf(%d : %d - %dn,i,a,c);move(i-1,b,a,c);move(i-1,b,a,c); int main()int main() int n; int n; scanf(%d,&n); scanf(%d,&n); move(n,1,2,3); move(n,1,2,3); return 0; return 0; 2014年 赵宗昌第一步：先借助第一步：先借助3柱把柱把1柱上面的柱上面的n-1个盘子移动