数据结构授课教学课件Recursion

1、Recursion The procedure of function call (stack application)rMain programsrrrs procedure 1rstprocedure 2rstprocedure 3Recursion SpecificationsA procedure or a function call itself directory or in-directory.Every recursive process consist of two parts:A smallest base case that is processed without re

2、cursion.A general method that reduces a particular case to one or more of the smaller cases, thereby making progress toward eventually reducing the problem all the way to the base case.Implementation of recursionEstablishing recursion working stack.Recursion -An exampleCalculate the factorials funct

3、ion of a positive integer n. 1 if n=0 n!= n*(n-1)! if n0Recursion -An example int factoria(int n)/* pre: n is a nonnegative integer Post: Return the value of the factorial of n. */ if(n=0) return 1; else return n*factorial(n-1);analyzing of recursion executionvoid print(int w) int i; if ( w=0) cout1

4、endl; else print(w-1); for(i=1;i=w;+i) coutw“, “1, move (n-1) disks from tower A to tower B first and then move the nth disk from A to C.Convert the problem from n disks Hanoi problem to (n-1) disks Hanoi problem until to 1 disk Hanoi problem. The Tower of HanoiMove(63,1,2,3) /move 63 disks from /to

5、wer 1 to 2 (tower 3 as temporary)Cout “Move disk 64 from tower 1 to tower 3. “endl;Move(63,2,3,1) /move 63 disks from /tower 2 to 3 (tower 1 as temporary)executionKeeping a recursion working stack to store: formal parameters n,x,y,z and return address.Return address is represented using line number.

6、n x y z return address main() int m; coutm; coutm“ disksn”; hanoi(m,A,B,C); void hanoi(int n,char x,char y,char z) /x: start,y:temp,z:finish(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) ABC1233 A B C 03 A B C 02 A C B 63 A B C 02 A C B 61 A B C

7、6ABC3 A B C 02 A C B 6main() int m; coutm; coutm“ disksn”; hanoi(m,A,B,C); void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 A C B 61 C A B 8ABC3 A B C 02 A C B 63 A B C 03 A B C 02 A C B 6 mai

8、n() int m; coutm; coutm“ disksn”; hanoi(m,A,B,C); void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 83 A B C 02 B A C 81 B C A 6ABC3 A B C 02 B A C 83 A B C 0main() int m; coutm; coutm“ d

9、isksn”; hanoi(m,A,B,C);void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 81 A B C 8ABC3 A B C 02 B A C 83 A B C 0Stack empty3 A B C 02 B A C 8Principles of recursion(1)Find the key step:

10、Begin by asking yourself “How can this problem be divided into parts?”. Be sure to keep your answer simple but generally applicable.Find the stopping ruleThe stopping rule indicates that the problem or a suitable part of it is done.Outline your algorithm.Combine the stopping rule and the key step, u

11、sing an if statement to select between them. You should now be able to write the main program and a recursive function that will describe how to carry the key step through until the stopping rule applies.Principles of recursion(2)Check termination.Verification that the recursion will always terminat

12、e. Start with a general situation and check that, in a finite number of steps, the stopping rule will be satisfied and the recursion terminate.Draw a recursion tree.The key tool for the analysis of recursive algorithms is the recursion tree. The height of the tree is closely related to the amount of

13、 memory that the program will require and the size of the tree reflects the number of times the key step will be done and hence the total time the program will use.When not to use recursionA recursive function can accomplish exactly the same tasks as an iterative function using a stack. E.g.Int fact

14、orial(int n) if(n=0) return 1; Else return n*factorial(n-1);Int factorial(int n) int count, product=1; for(count=1;count=2Int Fibonacci(int n)/* Fibonacci: recursive version */If(n=0) return 0;Else if(n=1) return 1;Else return Fibonacci(n-1)+Fibonacci(n-2)Int Fibonacci(int n)/* Fibonacci: iterative

15、version */ int last_but_one, last_value, current； if(n=0) return 0; else if(n=1) return 1; else last_but_one=0; last_value=1; for(int i =2; I=n; i+) current= last_but_one+ last_value; last_but_one=last_value; last_value=current; Assess of these two algorithmsThe amount of time used by the recursive function to calculate Fn grows exponentially with n.The amount of time used by iterative function is indirect proportion with n.Guidelines and conclusionsConsider the recursion tree:If the tree has a simple form, the iterative version may be better.If it involves duplicate tasks, then da