Recursion Review

Chia sẻ: Nguyễn Phpước Lộc | Ngày: | Loại File: PPT | Số trang:26

Thêm vào BST

Báo xấu

130
lượt xem 24
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Base cases. You must always have some base cases, which can be solved without recursion. Making progress. Recursive call must always be to a case that makes progress towards some base case. Design rule. Assume that all the recursive calls works.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Recursion Review

Recursion Review A Recursive Function: A function which invokes itself, either directly or indirectly. Direct Recursion: int Power(int base,int pow) { if (pow==0) return 1; else return base*Power(base,pow-1); } Indirect Recursion: int Power(int base,int pow) { if (pow==0) return 1; else return Multiply_Base_With_Power1Less(base,pow); } int Multiply_Base_With_Power1Less (int base,int pow) { return base * Power(base,pow-1); } 1
Recursion Review: Factorials Suppose there are some people called Mr. Factorial. They are identical. They know that 0! = 1. But they don’t know how to compute other factorials. Luckily 1. They know how to make recursive calls. 2. They know how to multiply 2 numbers. 3. And they know that: n! = n * (n-1)! 2
Recursion Review: Factorials So complicated. At the beginning, a I only know 3! = 3 * (3-1)!. 3! Mr. Factorial is Let me call another Mr. Factorial called to compute: to handle (3-1)! first. Then another Mr. So complicated. I only know 2! = 2 * (2-1)!. Factorial is called 2! Let me call another Mr. Factorial to compute: to handle (2-1)! first. Then another Mr. So complicated. Factorial is called I only know 1! = 1 * (1-1)!. 1! to compute: Let me call another Mr. Factorial to handle (1-1)! first. Then another Mr. This is easy. Factorial is called I know 0! is 1. 0! to compute: 3
Recursion Review: Factorials Now I can compute : Then this Mr. 3! = 3*2 3! = 3* the returned value =! 36 Factorial returns 6 2 Then this Mr. Now I can compute : 2! = 2*1 2! = 2* the returned value Factorial returns 2 2! =2 1 Then this Mr. Now I can compute : 1! = 1*1 Factorial returns 1 1! = 1* the returned value 1! =1 1 Then this Mr. This is easy. Factorial returns 1 I know 0! is 1. 0!0! 1 = 4
Writing Recursive Functions 3 rules for writing recursive functions: int RFactorial(int n) 1. Base cases. You must always have { if (n==0) some base cases, which can be return 1; solved without recursion. return (n * RFactorial(n-1)); 2. Making progress. Recursive call must } always be to a case that makes progress towards some base case. 3. Design rule. Assume that all the recursive calls works. (Very often it is difficult to track recursive calls, eg. Towers of Hanoi). Think of each recursive call as “somebody” you can trust – Just give him the order, don’t worry too much. 5
Tower of Hanoi Given some rods for stacking disks. The problem: Use fewest steps to move all disks Rules: from the source rod to the target (1) The disks must be stacked in without violating the rules through order of size. the whole process (given one (2) Each time move 1 disk. intermediate rod for buffering)? a source rod an intermediate rod a target rod 6
Tower of Hanoi Example 1: The process: To transfer one disk from A to C: Original with B as intermediate rod A B C 1 step: Move 1 disk from A to C A B C A B C 7
Tower of Hanoi Example 2: The process: To transfer 2 disks from A to C: Original with B as intermediate rod A B C 3 steps: Move 1 disk from A to B Move 1 disk from A to C Move 1 disk from B to C A B C 8
Tower of Hanoi Example 3: To transfer 3 disks from A to C: with B as intermediate rod How to do so? A B C Recall example 1: Transfer 1 disk from a source rod to a target using one intermediate rod. Or we say: move 1 topmost disk from a source rod to a target .. Recall example 2: Transfer 2 disks from a source rod to a target using one intermediate rod. Or we say: move 2 topmost disks from a source rod to a target .. 9
Tower of Hanoi Example 3: To transfer 3 disks from A to C: Towers(3, A, C, B) with B as intermediate rod Phase 1: Move 2 topmost Towers(2, A, B, C) disks from a source rod to the target (using one intermediate rod) Phase 2: Move 1 topmost Towers(1, A, C, B) disks from a source rod to the target (using one intermediate rod) Phase 3: Move 2 topmost Towers(2, __, __, __) disks from a source rod to the target (using one intermediate rod) 10
Tower of Hanoi Another View of Example 2: To transfer 2 disks from A to C: Towers(2, A, C, B) with B as intermediate rod Phase 1: Move 1 topmost Towers(1, A, B, C) disks from a source rod to the target (using one intermediate rod) Phase 2: Move 1 topmost Towers(1, A, C, B) disks from a source rod to the target (using one intermediate rod) Phase 3: Move 1 topmost Towers(1, B, C, A) disks from a source rod to the target (using one intermediate rod) 11
Tower of Hanoi The void Towers (int n, char Source, char Target, char Interm) { sif (n==1) olution : printf(“From %c to %c\n”, Source,Target); else { Towers(n-1, Source, Interm, Target); Towers(1, Source, Target, Interm); Towers(n-1, Interm, Target, Source); } } 12
Tower of Hanoi Towers (3,’A’,’C’,’B’) The void Towers (int n, char Source, char Target, char Interm) { sif (n==1) olution : printf(“From %c to %c\n”, Source,Target); else { Towers(n-1, Source, Interm, Target); Towers(1, Source, Target, Interm); Towers(n-1, Interm, Target, Source); } } 13
Recursive calls Result: void Towers (int n, char Source, char Target, char Interm) From A to C { if (n==1) From A to B printf(“From %c to %c\n”, Source,Target); From C to B else { Towers(n-1, Source, Interm, Target); (..) Towers(1, Source, Target, Interm); Towers(n-1, Interm, Target, Source); } } Towers (3,’A’,’C’,’B’) Towers (1,’A’,’C’,’B’) Towers (2,’A’,’B’,’C’) printf: From A to C Towers (1,’A’,’B’,’C’) printf: From A to B Towers (1,’A’,’C’,’B’) Towers (1,’C’,’B’,’A’) printf: From C to B Towers (2,’B’,’C’,’A’) 14
Recursive calls Result: void Towers (int n, char Source, char Target, char Interm) From to C FromAA to C { if (n==1) From AA to B From to B printf(“From %c to %c\n”, Source,Target); From C toto B From C B else From A to C { Towers(n-1, Source, Interm, Target); (..) (..) Towers(1, Source, Target, Interm); Towers(n-1, Interm, Target, Source); } } Towers (3,’A’,’C’,’B’) Towers (2,’A’,’B’,’C’) Towers (1,’A’,’C’,’B’) printf: From A to C Towers (2,’B’,’C’,’A’) 15
Recursive calls Result: void Towers (int n, char Source, char Target, char Interm) From A to C { if (n==1) From A to B printf(“From %c to %c\n”, Source,Target); From C to B else From AA to C From to C { Towers(n-1, Source, Interm, Target); From B to A (..) Towers(1, Source, Target, Interm); From B to C Towers(n-1, Interm, Target, Source); } From A to C } Towers (3,’A’,’C’,’B’) Towers (1,’B’,’A’,’C’) Towers (2,’A’,’B’,’C’) printf: From B to A Towers (1,’B’,’C’,’A’) Towers (1,’A’,’C’,’B’) printf: From B to C Towers (1,’A’,’C’,’B’) printf: From A to C Towers (2,’B’,’C’,’A’) 16
Recursive Calls and Returning void Towers (int n, char Source, char Target, char Interm) { if (n==1) printf(“From %c to %c\n”, Source,Target); else { Towers(n-1, Source, Interm, Target); Towers(1, Source, Target, Interm); Towers(n-1, Interm, Target, Source); } } Towers (1,’A’,’C’,’B’) Towers (1,’A’,’C’,’B’) Recursive Calls: Towers (2,’A’,’B’,’C’) Towers (1,’A’,’B’,’C’) Towers (2,’A’,’B’,’C’) Towers (1,’A’,’B’,’C’) Towers (1,’C’,’B’,’A’) Towers (1,’C’,’B’,’A’) Towers (3,’A’,’C’,’B’) Towers (1,’A’,’C’,’B’) Main() Towers (3,’A’,’C’,’B’) Towers (1,’A’,’C’,’B’) Towers Towers (1,’B’,’A’,’C’) Towers (1,’B’,’A’,’C’) Towers (1,’B’,’C’,’A’) Towers (1,’B’,’C’,’A’) Towers (2,’B’,’C’,’A’) Towers (2,’B’,’C’,’A’) Towers (1,’A’,’C’,’B’) Towers (1,’A’,’C’,’B’) 17
The Stack Memory Structure for Recursion Memory: In recursion, Towers(2,’A’,’B’,’C’) Each time a recursive function calls itself, an entirely new data area data area for that particular call must be allocated. Towers(3,’A’,’C’,’B’) The data area includes all parameters, local variables, and data area returning address, etc. main() The area is freed upon the call returns. data area The calls and returns of the recursive function form a stack: The most recent call of the function is the first one to return. Towers (1,’A’,’C’,’B’) Towers (2,’A’,’B’,’C’) Towers (1,’A’,’B’,’C’) Towers (1,’C’,’B’,’A’) Main() Towers (3,’A’,’C’,’B’) Towers (1,’A’,’C’,’B’) Towers (1,’B’,’A’,’C’) Towers (1,’B’,’C’,’A’) Towers (2,’B’,’C’,’A’) Towers (1,’A’,’C’,’B’) 18
The stack in memory to keep successive generations of local variables and parameters etc.: Towers(1,A,C,B) Towers(1,A,B,C) data area data area Towers(2,A,B,C) Towers(2,A,B,C) Towers(2,A,B,C) Towers(2,A,B,C) data area data area data area data area Towers(3,A,C,B) Towers(3,A,C,B) Towers(3,A,C,B) Towers(3,A,C,B) Towers(3,A,C,B) data area data area data area data area data area main() main() main() main() main() main() data area data area data area data area data area data area Towers (1,’A’,’C’,’B’) Towers (1,’A’,’C’,’B’) Recursive Calls: Towers (2,’A’,’B’,’C’) Towers (1,’A’,’B’,’C’) Towers (2,’A’,’B’,’C’) Towers (1,’A’,’B’,’C’) Towers (1,’C’,’B’,’A’) Main() Towers (3,’A’,’C’,’B’) Towers (3,’A’,’C’,’B’) Towers (1,’A’,’C’,’B’) Towers (1,’B’,’A’,’C’) Towers (1,’B’,’C’,’A’) Towers (2,’B’,’C’,’A’) Towers (1,’A’,’C’,’B’) 19
The stack in memory to keep successive generations of local variables and parameters: Towers(1,A,C,B) data area Towers(2,B,C,A) Towers(2,B,C,A) data area data area Towers(3,A,C,B) Towers(3,A,C,B) Towers(3,A,C,B) data area data area data area main() main() main() main() …. Empty data area data area data area data area Towers (1,’A’,’C’,’B’) Recursive Calls: Towers (2,’A’,’B’,’C’) Towers (2,’A’,’B’,’C’) Towers (1,’A’,’B’,’C’) Towers (1,’C’,’B’,’A’) Towers (3,’A’,’C’,’B’) Towers (1,’A’,’C’,’B’) Main() Towers (3,’A’,’C’,’B’) Towers (1,’A’,’C’,’B’) Towers (1,’B’,’A’,’C’) Towers (2,’B’,’C’,’A’) Towers (1,’B’,’C’,’A’) Towers (2,’B’,’C’,’A’) Towers (1,’A’,’C’,’B’) Towers (1,’A’,’C’,’B’) 20