Transcript 2-1 Factorial - A Case Study We begin the discussion of recursion

Chapter 2
Recursion
Objectives
Upon completion you will be able to:
• Explain the difference between iteration and recursion
• Design a recursive algorithm
• Determine when an recursion is an appropriate solution
• Write simple recursive functions
Data Structures: A Pseudocode Approach with C
1
How to writing repetitive algorithms


Iteration
Recursion


Is a repetitive process in which an algorithm
calls itself.
請同學區分這三個字 repetitive、 iterative、 recursive，
特別是看中文書的同學。
Data Structures: A Pseudocode Approach with C
2
2-1 Factorial - A Case Study
We begin the discussion of recursion with a case
study and use it to define the concept.
This section also presents an iterative and a
recursive solution to the factorial algorithm.
• Recursive Defined
• Recursive Solution
Data Structures: A Pseudocode Approach with C
3
Iterative

The definition involves only the algorithm parameter(s)
and not the algorithm itself.
Data Structures: A Pseudocode Approach with C
4
Recursive

A repetitive algorithm use recursion whenever the
algorithm appears within the definition itself.
Data Structures: A Pseudocode Approach with C
5
Data Structures: A Pseudocode Approach with C
6
Note that

Recursion is a repetitive process in which
an algorithm called itself.
Data Structures: A Pseudocode Approach with C
7
Data Structures: A Pseudocode Approach with C
8
Data Structures: A Pseudocode Approach with C
9
Which code is simpler?

Which one has not a loop?
Data Structures: A Pseudocode Approach with C
10
Calling a
recursive
algorithm
Data Structures: A Pseudocode Approach with C
11
2-2 Designing Recursive Algorithms
In this section we present an analytical
approach to designing recursive algorithms.
We also discuss algorithm designs that are not
well suited to recursion.
• The Design Methodology
• Limitation of Recusion
• Design Implemenation
Data Structures: A Pseudocode Approach with C
12
The Design Methodology

Every recursive call either solves a part of
the problem or it reduce the size of the
problem.
Data Structures: A Pseudocode Approach with C
13
The Design Methodology

Base case



The statement that “solves” the problem.
Every recursive algorithm must have a base
case.
General case


The rest of the algorithm
Contains the logic needed to reduce the size
of the problem.
Data Structures: A Pseudocode Approach with C
14
Rules for designing a recursive
algorithm
1. Determine the base case.
2. Determine the general case.
3. Combine the base case and the general
cases into an algorithm.
Data Structures: A Pseudocode Approach with C
15
Combine the base case and the
general cases into an algorithm


Each call must reduce the size of the
problem and move it toward the base case.
The base case, when reached, must
terminate without a call to the recursive
algorithms; that is, it must execute a
return.
Data Structures: A Pseudocode Approach with C
16
Limitations of recursion

You should not use recursion if the answer
to any of the following questions is no:
1. Is the algorithm or data structure naturally
suited to recursion?
2. Is the recursive solution shorter and more
understandable?
3. Does the recursive solution run within
acceptable time and space limits?
Data Structures: A Pseudocode Approach with C
17
Design implementation – reverse
keyboard input
Data Structures: A Pseudocode Approach with C
18
※ 請注意 print data
在什麼時候執行
data=6
data=20
data=14
data=5
Data Structures: A Pseudocode Approach with C
19
2-3 Recursive Examples
Four recursive programs are developed and
analyzed. Only one, the Towers of Hanoi, turns
out to be a good application for recursion.
• Greatest Common Divisor
• Fiboncci Numbers
• Prefix to Postfix Conversion
• The Towers of Honoi
Data Structures: A Pseudocode Approach with C
20
Slide 05
GCD design
a
if b  0 

gcd( a, b)  
b
if a  0 
gcd( b, a mod b) otherwise 
Greatest Common Divisor Recursive Definition
Data Structures: A Pseudocode Approach with C
21
Pseudocode
歐基里德
輾轉相除法
Data Structures: A Pseudocode Approach with C
22
GCD C implementation
Data Structures: A Pseudocode Approach with C
23
gcd(10, 25)
gcd(25, 10)
gcd(10, 5)
gcd(5, 0)
Data Structures: A Pseudocode Approach with C
24
Another G.C.D. Recursive Definition
Data Structures: A Pseudocode Approach with C
25
Fibonacci numbers



在費波那西的〈算經〉中提到一個問題：
假如一對兔子，一個月後能生產一對兔子，
而新生兔子在一個月後便具備生育能力，
也能生下一對兔子。
那麼若從一對兔子開始，一年之後將會有
多少對兔子？
Data Structures: A Pseudocode Approach with C
26
Fibonacci numbers
Data Structures: A Pseudocode Approach with C
27
Fibonacci numbers -- 費式數


Each number is the sum of the previous
two numbers.
The first few numbers in the Fibonacci
series are

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
Data Structures: A Pseudocode Approach with C
28
Fibonacci numbers -- 費式數
Data Structures: A Pseudocode Approach with C
29
Fibonacci numbers
Data Structures: A Pseudocode Approach with C
30
Fibonacci numbers – an example
Data Structures: A Pseudocode Approach with C
31
0 represents .T.
Data Structures: A Pseudocode Approach with C
32
(Continued)
Data Structures: A Pseudocode Approach with C
33
Analysis
Data Structures: A Pseudocode Approach with C
34
We omit


Prefix to Postfix Conversion
The Towers of Honoi
Data Structures: A Pseudocode Approach with C
35
HW2


Write a recursive algorithm to calculate
the combination of n objects taken k at a
time.
Due date : (甲：941012、乙：941012)
Data Structures: A Pseudocode Approach with C
36
2-3 Recursive Examples
Four recursive programs are developed and
analyzed. Only one, the Towers of Hanoi, turns
out to be a good application for recursion.
•The Towers of Honoi
Data Structures: A Pseudocode Approach with C
37
Slide 05
Towers of Hanoi Problem:




Invented by French mathematician Lucas
in 1880s.
Original problem set in India in a holy
place called Benares.
There are 3 diamond needles fixed on a
brass plate. One needle contains 64 pure
gold disks. Largest resting on the brass
plate, other disks of decreasing diameters.
Called tower of Brahma.
Data Structures: A Pseudocode Approach with C
38
Towers of Hanoi Problem:

Priests are supposed to transfer the disks
from one needle to the other such that at




no time a disk of larger diameter should sit on
a disk of smaller diameter.
Only one disk can be moved at a time.
Later setting shifted to Honoi, but the
puzzle and legend remain the same.
How much time would it take? Estimate…..
Data Structures: A Pseudocode Approach with C
39
Data Structures: A Pseudocode Approach with C
40
Towers of Hanoi Problem:

Today we know that we need to have
64
2 -1
Data Structures: A Pseudocode Approach with C
41
Recursive Towers of Hanoi Design


Find a pattern of moves.
Case 1:

move one disk from source to destination
needle.
Data Structures: A Pseudocode Approach with C
42
Move two disks

Case 2:



Move one disk to auxiliary needle.
Move one disk to destination needle.
Move one disk to from auxiliary to destination
needle.
Data Structures: A Pseudocode Approach with C
43
Data Structures: A Pseudocode Approach with C
44
Move three disks

Case 3:



Move two disks from source to auxiliary
needle.
Move one disk from source to destination
needle.
Move two disks from auxiliary to destination
needle.
Data Structures: A Pseudocode Approach with C
45
(Continued)
Move two disks from source to auxiliary needle.
Move two disks from auxiliary to destination needle.
Data Structures: A Pseudocode Approach with C
46
Algorithm Tower of Hanoi

Towers (numDisks, source, dest, auxiliary)




numDisks is number of disks to be moved
source is the source tower
dest is the destination tower
auxiliary is the auxiliary tower
Data Structures: A Pseudocode Approach with C
47
Data Structures: A Pseudocode Approach with C
48
Generalize Tower of Hanoi

General case


Base case


Move n-1 disks from source to auxiliary.
Move one disk from source to destination.
General case

Move n-1 disks from auxiliary to destination.
Data Structures: A Pseudocode Approach with C
49
Data Structures: A Pseudocode Approach with C
50
Data Structures: A Pseudocode Approach with C
51
Data Structures: A Pseudocode Approach with C
52
Data Structures: A Pseudocode Approach with C
53
Data Structures: A Pseudocode Approach with C
54
Data Structures: A Pseudocode Approach with C
55