Transcript return

Recursion
1
CHAPTER TWO
 Recursion: A recursive function is a function that calls itself.
 Two functions A and B are mutually recursive, if A calls B









and B calls A.Recursion can always replace iteration (looping).
n!
A simple example: Factorial.
Factorial(0) = 1
(By definition)
Factorial(1) = 1
Factorial(2) = 2*1
Factorial(3) = 3*2*1
Factorial(4) = 4*3*2*1
Factorial(5) = 5*4*3*2*1
Factorial(n) = n * n-1 * n-2 * ... 1
2
DEFINITION OF
 Factorial(n) =
{
n!
1
if n = 0
n * Factorial(n-1)
if n > 0
 This recursive definition needs for a recursive
implementation.
3
Recursive implementation
int factorial (int n)
{
if (n == 0)
return 1;
else
return n * factorial(n - 1);
}
4
How to understand recursion
 Every time a recursive function is called,
that’s like it is a completely separate
function.
 Just ignore the fact that this function was
called by itself.
 Specifically, if “factorial” calls itself, then
there are two parameters “n” that have
NOTHING to do with each other.
5
EXAMPLE factorial(3)
factorial(3): n = 3 calls factorial(2)
factorial(2): n = 2 calls factorial(1)
factorial(1): n = 1 calls factorial(0)
factorial(0): returns 1 to factorial(1).
Inside factorial(1),
1 * factorial(0) becomes: 1 * 1
factorial(1): returns 1 to factorial(2),
Inside factorial(2), 2 * factorial(1) becomes: 2 * 1
6
EXAMPLE factorial(3) CONTINUED
factorial(2) returns 2 to factorial(3).
Inside factorial(3), 3 * factorial(2) becomes: 3 * 2
So, inside factorial(3), the return value is 3 * 2 = 6.
This is what will be returned to the program.
cout << factorial(3) ; // writes 6 to the screen.
7
What problems can be recursively solved?
The following conditions should be fulfilled:
1 - The problem can be decomposed into several
problems such that (at least) one of them is of
the “same kind” as the initial problem but
“simpler” and all the others are “easy”; and
2 - If you keep deriving simpler and simpler
problems of the “same kind”, you will eventually
reach an “easy” problem.
8
Why factorial () can be recursive?
1 - factorial(n) is decomposed into two problems:
A multiplication and factorial(n-1) is a problem of
the same kind as factorial(n), but factorial(n-1) is
Also simpler than factorial(n).
1)factorial(n) = n * factorial(n - 1) --- if n > 0
2)factorial(n) = 1 --- if n = 0
2 - If we keep reducing the argument of factorial( )
more and more, eventually, we will get factorial(0)
which is “easy” to solve.
9
Factorial Illustration
cout << Fact(3);
6
Return 3*Fact(2)
3*2
int Fact(int N)
{
Return 2*Fact(1)
2*1
if (N= =0)
Return 1*Fact(0)
1*1
return 1;
else
return N * Fact(N-1);
}
Return 1
Fact(3)
10
Factorial Illustration cont’d
N=3
A: Fact(N-1) = ?
Return ?
N=3
A: Fact(N-1) = ?
Return ?
N=3
A: Fact(N-1) = ?
Return ?
N=2
A: Fact(N-1) = ?
Return ?
N=2
A: Fact(N-1) = ?
Return ?
N=1
A: Fact(N-1) = ?
Return ?
N=3
A: Fact(N-1) = ?
Return ?
N=2
A: Fact(N-1) = ?
Return ?
N=1
A: Fact(N-1) = ?
Return ?
N=3
A: Fact(N-1) = ?
Return ?
N=2
A: Fact(N-1) = ?
Return ?
N=1
A: Fact(N-1) = ?
Return ?
N=3
A: Fact(N-1) = ?
Return ?
N=2
A: Fact(N-1) = ?
Return ?
N=1
A: Fact(N-1) = 1
Return ?
N=0
Return ?
N=0
Return 1
N=0
Return 1
11
Factorial Illustration cont’d
N=3
A: Fact(N-1) = ?
Return ?
N=2
A: Fact(N-1) = ?
Return ?
N=1
A: Fact(N-1) = 1
Return 1
N=3
A: Fact(N-1) = ?
Return ?
N=2
A: Fact(N-1) = 1
Return ?
N=1
A: Fact(N-1) = 1
Return 1
N=3
A: Fact(N-1) = ?
Return ?
N=2
A: Fact(N-1) = 1
Return 2
N=1
A: Fact(N-1) = 1
Return 1
N=3
A: Fact(N-1) = 2
Return ?
N=2
A: Fact(N-1) = 1
Return 2
N=1
A: Fact(N-1) = 1
Return 1
N=3
A: Fact(N-1) = 2
Return 6
N=2
A: Fact(N-1) = 1
Return 2
N=1
A: Fact(N-1) = 1
Return 1
N=0
Return 1
N=0
Return 1
N=0
Return 1
N=0
Return 1
N=0
Return 1
12
Example: Writing an array backwards
 Given an array of characters, and we want to write
its elements backwards to the screen, i.e., starting
with the last character.
 Of course this can be done with a
 for (x = ArraySize-1; x >= 0 ; --x) loop, but we will do
it recursively.
 Let’s try to decompose the problem.
13
Decomposition
 1 - Writing an array of length “n” can be decomposed
into writing a single character (that’s easy) and writing
an array of length “n-1” backwards, which is a problem
of the same kind as writing an array of length “n”, but
it’s simpler”.
 2 - If we keep reducing the length of the array that we
have to write backwards, we will eventually end up with
an array of size 1. That is: a character, and writing a
character is “easy”.
 EVEN BETTER, we can go to an array of size ZERO and
then we have to do NOTHING.
14
Write the function
Still, nothing in this description results in something written
backward! We refine:
An array is written backward by FIRST writing its last
element, and then writing the array that is left backwards. If
we come down to an array of size 0, we do nothing.
void writebackward(char S[], int size)
{
if (size > 0) {
cout << S[size-1];
writebackward(S, size-1);
}
}
15
Execute the function
Let’s trace through this with the following
example:
Assume that ST contains the characters C A T.
writebackward(ST, 3) is now called.
Within writebackward( ) we have therefore:
ST:
C
A
T
3
16
Step by step
cout << S[3-1]; will send to the screen: T
Then comes the recursive call to
writebackward(S,2)
Note that S is never changed in the process.
writebackward(S,2) will first do
cout << S[2-1]; which will write to screen: A
Then comes the recursive call to
writebackward(S,1)
writebackward(S,1) will first do
cout << S[1-1]; which will write to screen: C
Then comes the recursive call to
17
Last step
writebackward(S,0)
Writebackward(S,0) will do NOTHING.
Note that we have already written TAC to the screen.
Note that the program does not end here.
Take a look back at the code of
writebackward( ).
You see that NOTHING is done in
writebackward( ) AFTER the recursive call.
18
writebackward( ) Return Path
• writebackward(S,0) returns to writebackward(S,1)
• writebackward(S,1) has nothing left to do,
returns to its caller, writebackward(S,2).
• writebackward(S,2) has nothing left to do,
returns to its caller, writebackward(S,3).
• When writebackward(S,3) returns, the program
is finished.
19
WriteBackWard(S, size)
20
S = “cat”
Size = 3
S = “cat”
Size = 3
S = “cat”
Size = 2
S = “cat”
Size = 3
S = “cat”
Size = 2
S = “cat”
Size = 1
S = “cat”
Size = 3
S = “cat”
Size = 2
S = “cat”
Size = 1
S = “cat”
Size = 0
S = “cat”
Size = 3
S = “cat”
Size = 2
S = “cat”
Size = 1
S = “cat”
Size = 0
S = “cat”
Size = 3
S = “cat”
Size = 2
S = “cat”
Size = 1
S = “cat”
Size = 0
S = “cat”
Size = 3
S = “cat”
Size = 2
S = “cat”
Size = 1
S = “cat”
Size = 0
20
Another solution
Another solution to the writeback problem:
void writeback(char S[], int size, int pos)
{
if (pos < size) {
writeback(S, size, pos+1);
cout << S[pos];
}
{
21
Initial call
We need to call this as follows:
Assume again that ST contains the characters
CAT
writeback(ST, 3, 0);
Note that this procedure does SOMETHING
after the recursive call. This is harder.
22
Nothing happens at the beginning
Inside of writeback(ST, 3, 0) nothing happens
before the recursive call. The recursive call
will be:
writeback(S, 3, 1)
23
Nothing
Inside of writeback(S, 3, 1) nothing happens
before the recursive call. The recursive call
will be writeback(S, 3, 2).
Inside of writeback(S, 3, 2) nothing happens
before the recursive call. The recursive call
will be writeback(S, 3, 3).
24
writeback( ) Return Path
• writeback(S, 3, 3) will not do anything, because
the IF condition evaluates to FALSE.
• writeback(S, 3, 3) returns to writeback(S, 3, 2).
• writeback(S, 3, 2) sends T to the screen.
• writeback(S, 3, 2) returns to writeback(S, 3, 1).
• writeback(S, 3, 1) sends A to the screen.
• writeback(S, 3, 1) returns to writeback(S, 3, 0).
• writeback(S, 3, 0) sends C to the screen.
• writeback(S, 3, 0) returns to the main program.
25
WriteBackWard(S)
WriteBackWard(S)
WriteBackWard(S minus last character)
void WriteBackWard(char S[])
{cout <<"Enter WriteBackWard with string: " << S << endl;
if (strlen(S)==0){}
else { cout << "About to write last character of string:" << S << endl;
cout <<S[strlen(S)-1]<<endl;;
S[strlen(S)-1]='\0';
WriteBackWard(S);
}
cout << "Leave WriteBackWard with string:" << S << endl;
}
26
WriteBackWard(S)
S = “cat”
S = “cat”
S = “cat”
S = “ca”
S = “ca”
S = “c”
S = “cat”
S = “ca”
S = “c”
S=“”
S = “cat”
S = “ca”
S = “c”
S=“”
S = “cat”
S = “ca”
S = “c”
S=“”
S = “cat”
S = “ca”
S = “c”
S=“ ”
27
Output stream
Enter WriteBackWard with string: cat
About to write last character of string: cat
WriteBackWard(S)
t
Enter WriteBackWard with string: ca
About to write last character of string: ca
a
Enter WriteBackWard with string: c
About to write last character of string: c
C
Enter WriteBackWard with string:
About to write last character of string:
Leave WriteBackWard with string:
Leave WriteBackWard with string: c
Leave WriteBackWard with string: ca
Leave WriteBackWard with string: cat
28
POWER
X^n = 1
IF n = 0 Base Case
X^n = X*X^(n-1)
IF n > 0 Recursive Case
This can be translated easily into C++.
However, we can do better:
X^n = 1
IF n = 0
X^n = X * square of X^(n / 2) IF n is odd
X^n = square of X^(n / 2)
IF n is even
29
The function
int power(int X, int N)
{
if (N == 0)
return 1;
else {
int HalfPower = power(X, N/2);
if (N % 2 == 0)
return HalfPower * HalfPower; // Even n
else
return X * HalfPower * HalfPower; // Odd n
}
}
30
FIBONACCI SEQUENCE
A sequence of numbers is defined as follows:
The first number is 1. The second number is 1.
Every other number is the sum of the two
numbers before it.
1 1 2 3 5 8 13 21 34 55 89
fib(1) = 1
Base Case
fib(2) = 1
Base Case
fib(n) = fib(n-1) + fib(n-2)
n>2
This is a recursion that uses TWO base cases, and it breaks
down a problem into TWO simpler problems of the same
kind.”
31
The Function
int fib(int n)
{
if (n <= 2)
return 1;
else
return fib(n-1) + fib(n-2);
}
The recursive implementation is, however, TERRIBLY inefficient, and
is not recommended.
fib(7) will call fib(3) 5 times! What a waste!
32
An (artificial) example with rabbits.
- Rabbits never die.
- Rabbits always give birth to twins, male and
female.
- A couple of rabbits give birth to twins at the first
day of every month, starting at age 3 months.
- We start with ADAM rabbit and EVE Rabbit.
33
The couples of rabbits are Fibonacci numbers
Month
1:
Couples:1 Adam, Eve
2:
1 Adam, Eve
3:
2 A&E and twins 1
4:
3 A&E twins 1, twins 2
5:
5 A&E, twins 1, twins 2
twins 3 (from A&E) and
twins 4 (from twins 1)
6:
8 A&E, twins 1-4
twins 5 (from A&E), twins 6
(from 1), twins 7 (from 2)
Surprise!? These are the Fibonacci numbers.
34
The Mad Scientist’s Problem
 We want to make a chain out of pieces of
Lead and Plutonium.
 The chain is supposed to be of length n.
 However, there is a problem: if we put two
pieces of Plutonium next to each other,
the whole chain will explode.
 How many safe chains are there?
(Note: These are linear chains.)
35
Analysis
C(n) = Number of Safe Chains of length n.
L(n) = The number of safe chains of length n that END with a piece of
lead.
P(n) = The number of safe chains of length n that END with a piece of
Plutonium.
Example: Length = 3
s
LLL
s
LLP
s
LPL
u
LPP
s
s
u
u
PLL
PLP
PPL
PPP
36
Analysis cont’d
 The total number of chains must be the sum of those
that end with Lead and those that end with Plutonium.
 C(n) = L(n) + P(n)
 Now we look at the two terms, assuming that we add
one new piece to the end.
 Given are all chains of length n-1. There are again C(n-1)
of those. To which of them can we add a piece of lead?
To ALL of them.
 Therefore, L(n) = C(n-1)
37
Analysis Cont’d
 Given are all chains of length n-1. There are again C(n-1)
of those. To which of them can we add a piece of
Plutonium?
 Only to those that END with a piece of LEAD!! There
are L(n-1) of those. Therefore,
 P(n) = L(n-1)
C(n) = L(n) + P(n) = C(n-1) + L(n-1) = C(n-1) + C(n-2)
 This is the Fibonacci formula. However, we have slightly different
base cases here.
 C(1) = 2
 C(2) = 3
P or L
PL of LP or LL
 Back to our example:
 C(3) = C(2) + C(1) = 3 + 2 = 5.
 That’s exactly what we had before.
38
Mr. Spock’s Dilemma
There are n planets in an unexplored planetary
system, but there is fuel for only k visits.
How many ways are there for choosing a group of
planets to visit?
Let’s think about a specific planet, planet X.
Either we visit X, or we don’t visit X.
C(n, k) = {number of ways to chose k out of n}
If we visit X, then we have n-1 choices left, but only
fuel for k-1 visits.
If we don’t visit X, then we have n-1 choices left, but
we still have fuel for k visits.
39
Analysis
 The total number of ways to choose must be the sum
of the total number of trips that include the planet X
and the total number of trips that do not include the
planet X.
 C(n, k) = C(n-1, k-1) + C(n-1, k)
 This is clearly recursive. Both sub-problems are of the
same kind and simpler. But are there base cases?
 C(n-1, k-1) eventually
C(n-k, 0)
 C(n-1, k)
eventually
C(k, k)
 (n must be greater than k, otherwise we visit all
planets, and the problem is not a problem.)
40
Last analysis
 C(k,k) = 1 (There is only one way to choose k
planets out of k planets!)
 C(n,0) = 1 (There is only one way to select no
planet.)
 This is a little abstract. We can use C(n, 1) = n
(There are n ways to select 1 planet of n.)
41
The function
We are ready for the recursive definition:
1
IF k = 0
C(n,k) = 1
IF k = n
C(n-1, k-1) + C(n-1, k)
IF 0 < k < n
0
IF k > n
int C(int n, int k)
{
if (k > n)
return 0;
else if (k == n)
return 1;
else if (k == 0)
return 1;
else
return C(n-1, k-1) + C(n-1, k);
}
42
C(4, 2)
C(4,2)
Return C(3,1) + C(3,2)
C(3,1)
Return C(2,0) + C(2,1)
C(2,0)
Return 1
C(2,1)
Return C(1,0) + C(1,1)
C(1,0)
Return 1
C(1,1)
Return 1
C(3,2)
Return C(2,1)) + C(2,2)
C(2,1)
Return C(1,0) + C(1,1)
C(1,0)
Return 1
C(2,2)
Return 1
C(1,1)
Return 1
The recursive call that C(4,2) generates
43
A game for guessing number
1. I think of a number between 1 -100.
2. When you guess one, I tell you the number
I thought is larger or less than the one you
guessed.
3. Continue step 2 till you guess the right
number I though of.
Write the number of times you guessed.
44
Binary Search
How do you find something efficiently in a
phone book? Open the phone book in the
middle. If what you are looking for is in the
first half, then ignore the second half and
divide the first half again in the middle. Keep
doing this until you find the page. Then
divide the page in half, etc.
45
Binary Search
More formally: Given is A, an array of n numbers
We want to verify whether V is in the array.
IF n ==1 THEN {check whether the number is
equal to V }
ELSE BEGIN { Find the midpoint of A }
IF {V is greater than the A[midpoint]}
THEN {Search recursively in the second half}
ELSE {Search recursively in the first half}
46
The function
int bins(int A[], int V, int fi, int la)
{
if (fi > la) return -1;
else {
int mid = (fi + la) / 2;
if (V == A[mid]) return mid;
else if (V < A[mid])
return bins(A,V,fi,mid-1);
else
return bins(A,V,mid+1,la);
}
}
47
Discuss
Notes: We always pass the whole array in.
These define the active part of the array:
- fi ... first
- la ... last
The return value -1 means that the number was not found.
Example:
Array A contains the numbers
0
1
1
5
2
9
3
13
4
17
5
19
6
23
We will look for V = 19 first, and V = 21 later.
cout << bins(A,19,0,6);
48
The process of search
1 5 9 13 17 19 23 = A; 19 = V
fi
m
la
fi m la
Note how we quickly found it!
1 5 9 13 17 19 23 = A , 21 = V
fi
m
la
fi m la
fi, m, la
la fi
Last is now before first and we stop.
49
Attentions!
Warning: Two common mistakes
(1): CORRECT: mid = (fi+1a)/2;
WRONG: mid = (A[fi] + A[la])/2;
(2): CORRECT: return bins(A, V, mid+1, la);
WRONG: return bins(A, V, mid, la);
50
Efficiency on large arrays
 Note: Let’s say we have an array of 1,000,000
sorted numbers. (It’s better if it has 2^20
elements, but that’s about 1,000,000.)
 The first decision eliminates approx. 500,000!
 The second decision eliminates another
250,000 numbers.
 After about 20 runs through the loop, we found
it. Sequential search might need to go through
all 1,000,000 elements. (1,000,000 loops)
 What an improvement!
51
Searching the maximum in an Array
if (A has only one item)
MaxArray(A) is the item in A
else if (A has more than one item)
MaxArray(A) is the maximum of MaxArray(left half of A)
and MaxArray(right half of A)
MaxArray(A)
MaxArray(left half of A)
MaxArray(right half of A)
Recursive solution to the largest-item problem
52
Searching in Array
MaxArray(<1,6,8,3>)
Return Max(MaxArray(<1,6>), MaxArray(<8,3>))
MaxArray(<1,6>)
MaxArray(<8,3>)
Return Max(MaxArray(<1>), MaxArray(<6>)) Return Max(MaxArray(<8>), MaxArray(<3>))
MaxArray(<1>)
Return 1
MaxArray(<6>)
Return 6
MaxArray(<8>)
Return 8
MaxArray(<3>)
Return 3
The recursive calls that MaxArray(<1,6,8,3>) generates
53
Tower of Hanoi
http://wipos.p.lodz.pl/zylla/games/hanoi3e.html
SolveTowers(Count, Source, Destination, Spare)
{ if (Count is 1)
Move a disk directly from source to Destination)
else
{ SolveTowers(Count-1, Source, Spare, Destination)
SolveTowers(1, Source, Destination, Spare)
SolveTowers(Count-1, Spare, Destination, Source)
}
}
54
Tower of Hanoi
SolveTowers(3, A, B, C)
SolveTowers(2, A, C, B)
SolveTowers(1, A, B, C)
SolveTowers(1, A, B, C)
SolveTowers(2, C, B, A)
SolveTowers(1, C, A, B)
SolveTowers(1, A, C, B)
SolveTowers(1, B, C, A)
SolveTowers(1, C, B, A)
SolveTowers(1, A, B, C)
The order of recursive calls that results from SolveTowers(3, A, B, C)
55
Recursion and Efficiency
 The function call overhead
 The inefficiency of some recursive algorithm
56
Use iterative (Example)
 int interativeRabbit(int n)
{
 int prev=1, curr=1, next=1;
 for (int i = 3; i <=n; ++i)
 { next = prev+curr;

prev = curr;

curr = next;
 }
 return next;
}
57
Summary
 Recursion solves a problem by solving a smaller
problem of the same type
 Four questions:
 How can you define the problem in terms of a smaller
problem of the same type?
 How does each recursive call diminish the size of the
problem?
 What instance(s) of the problem can serve as the base
case?
 As the problem size diminishes, will you reach a base
case?
58
Summary
 To construct a recursive solution, assume a recursive
call’s postcondition is true if its precondition is true
 The box trace can be used to trace the actions of a
recursive method
 Recursion can be used to solve problems whose
iterative solutions are difficult to conceptualize
59
Summary
 Some recursive solutions are much less efficient than
a corresponding iterative solution due to their
inherently inefficient algorithms and the overhead of
function calls
 If you can easily, clearly, and efficiently solve a
problem by using iteration, you should do so
60