Lecture 8

Recursion

The Mirrors
Lecture Outline
 Recursion: Basic Idea, Factorial
 Iteration versus Recursion
 How Recursion Works
 Recursion: How to
 More Examples on Recursion
 Printing a Linked List (in Reverse)
 Choosing k out of n Items
 Tower of Hanoi
 Fibonacci Numbers
 Binary Search
 Permute Strings

[ CS1020E AY1617S1 Lecture 8 ]

2
Recursion: Basic Idea
 The process of solving a problem with a function
that calls itself directly or indirectly
 The solution can be derived from solution of smaller problem of
the same type
 Example: Factorial
 Factorial(4) = 4 * Factorial(3)

 This process can be repeated

 e.g. Factorial(3) can be solved in term of Factorial(2)

 Eventually, the problem is so simple that it can solve

immediately
 e.g. Factorial(0) = 1

 The solution to the larger problem can then be derived

from this …
[ CS1020E AY1617S1 Lecture 8 ]
3
Recursion: The Main Ingredients
 To formulate a recursive solution:
 Identify the “simplest” instance
The base case(s) that can be solved without recursion
 Identify “simpler” instances of the same problem
The recursive case(s) that requires recursive calls to
solve them
 Identify how the solution from the simpler problem can help to
construct the final result

 Be sure we are able to reach the “simplest” instance

 So that we will not get an infinite recursion

[ CS1020E AY1617S1 Lecture 8 ]

4
Example: Factorial
 Let’s write a recursive function factorial(k)
that finds k!

 Base Case:
 Returns 1 when k = 0
 Corresponding C/C++ code:
if (k == 0)
return 1;

 Recursive Case:
 Returns k * (k-1)!
return k * factorial(k-1);

[ CS1020E AY1617S1 Lecture 8 ]

5
 Example: Factorial (code)
 Full code for factorial:
Max k is 20 before
it overflows Base Case:
factorial(0) = 1
long factorial(int k) {
if (k == 0)
return 1;
else
return k * factorial(k-1);
}

Recursive Case:
factorial(k) = k * factorial(k–1)

[ CS1020E AY1617S1 Lecture 8 ]

6
Understanding Recursion
 A recursion always goes through two phases:
 A wind-up phase:
 When the base case is not satisfied, i.e. function calls itself
 This phase carries on until we reach the base case

 An unwind phase:
 The recursively called functions return their values to previous
“instances” of the function call
 i.e. the last function returns to its parent (the 2nd last
function), then the 2nd last function returns to the 3rd last
function, and so on
 Eventually reaches the very first function, which computes the
final value

[ CS1020E AY1617S1 Lecture 8 ]

7
 Factorial: Wind-up Phase
 Let’s trace the execution of factorial(3)
(factorial abbreviated as fact)

k is not zero
fact( 3 ) returns 3 * fact( 2 )
k = 3

fact( 2 ) k is not zero

returns 2 * fact( 1 )
k = 2

k is not zero
long factorial(int k){ fact( 1 ) returns 1 * fact( 0 )
if (k == 0) k = 1
return 1;
else
return k * fact( 0 )
factorial(k-1);
k = 0
}
[ CS1020E AY1617S1 Lecture 8 ]
8
 Factorial: Unwind Phase
long factorial(int k){
if (k == 0)
return 1;
else
return k *
factorial(k-1);
k is not zero }
fact( 3 ) return 3 * fact(2)
return k = 3
3 * 2
= 6
fact( 2 ) k is not zero
return 2 * fact( 1 )
return 2 * 1 k = 2
= 2

fact( 1 ) k is not zero

return 1 * 1 return 1 * fact(0)
k = 1
= 1

k is zero fact( 0 )
return 1 k = 0

[ CS1020E AY1617S1 Lecture 8 ]

9
factorial(3) 6
long factorial(int k) { k
if (k == 0)
3
return 1;
else
2
return k * factorial(k-1);
} long factorial (int k) {
if (k == 0) k
return 1; 2
factorial(2) else
return k * factorial(k-1)
; 1

} long factorial (int k) {

if (k == 0) k
return 1; 1
else
factorial(1) return k * factorial(k-1) 1
}
long factorial(int k) {
if (k == 0)
k
return 1;
factorial(0) else 0
…………….

[ CS1020E AY1617S1 Lecture 8 ]

10
Recursions vs. Loops
 Many (simple), but not all, recursions essentially
accomplish a loop (iterations)
 Recursions are usually much more elegant than
its iterative equivalent
 It is conceptually simple
 Hence easier to implement
 However iterative version using loops for such
recursions is usually faster
 Common practice
 If we convert our recursion to iterative version,
we will generally do so

[ CS1020E AY1617S1 Lecture 8 ]

11
Recursive vs. Iterative Versions
long factorial(int k) {
int j, term;

term = 1;
for (j = 2; j <= k; j++)
term *= j;

return term;
} Iterative
Version

long factorial(int k) {
if (k == 0)
return 1;
else
return k * factorial(k-1);
}
Recursive
Version
[ CS1020E AY1617S1 Lecture 8 ]
12
 Example: Linked List Printing
 Print out the whole list given the pointer to a
ListNode
void printLL(ListNode *n){ head
if (n != NULL) {
cout << n->item; printLL
printLL(n->next); 5
}
} printLL
8
printLL

Output: 9

5 8 9 printLL

[ CS1020E AY1617S1 Lecture 8 ]

13
 Example: Linked List Printing
 How to print out the whole list in reverse order?

void printLL(ListNode *n){

head
if (n != NULL) {
printLL(n->next); printLL
cout << n->item; 5
}
} printLL
8
printLL
Output: 9
printLL
9 8 5

[ CS1020E AY1617S1 Lecture 8 ]

14
Example: Tower of Hanoi

initial state

A B C

 How do we move all the disks from pole “A” to pole

“B”, using pole “C” as temporary storage
 Move one disk at a time
 Each disk must not rest on top of a smaller disk

final state
A B C
[ CS1020E AY1617S1 Lecture 8 ]
15
 Tower of Hanoi: Recursive Solution
N Original
N-1
Problem
Size = N
Can be
solved by
… … …
Recursive
Case Phase 1
N-1
Size = N – 1

Base Case Phase 2

Size = 1

… … …
Recursive
N-1 Phase 3
Case
Size = N - 1
[ CS1020E AY1617S1 Lecture 8 ]
16
Tower of Hanoi: Solution
void tower(int N, char A, char B, char C) {
if (N == 1)
move(A, B);
else {
tower(N-1, A, C, B);
move(A, B);
tower(N-1, C, B, A); Perform the “move”.
} Many implementations.
} Below is one possibility.

void move(char s, char d) {

cout << "move from " << s << " to " << d << endl;
}

[ CS1020E AY1617S1 Lecture 8 ]

17
Number of Moves Needed
Num of Num of moves, Time
discs, n f(n) (1 sec per move)

1 1 1 sec

2 3 3 sec

3 3+1+3 = 7 7 sec

4 7+1+7 = 15 15 sec

5 15+1+15 = 31 31 sec

6 31+1+31 = 63 1 min

… … …

16 65,536 18 hours
32 4.295 billion 136 years Note the pattern
64 1.8 * 10^10 billion 584 billion years f(n) = 2n − 1

[ CS1020E AY1617S1 Lecture 8 ]

20
Example: Combinatorial
 How many ways can we choose k items out of n
items?
choose k-1 out of n-1
X selected
or Recursive
choose k out of n
Cases
X not selected
choose k out of n-1
k==n k==0
int choose(int k, int n) {
if (k > n) return 0;
1 way 1 way if (k == n || k == 0) return 1;
return choose(k-1, n-1) +
Base Cases choose(k , n-1);
}

[ CS1020E AY1617S1 Lecture 8 ]

22
 Execution Trace: choose(2, 4)
c(2,4)
ret c(1,3) + c(2,3)

c(1,3) c(2,3)
ret c(0,2) + c(1,2) ret c(1,2) + c(2,2)

c(0,2) c(1,2) c(1,2) c(2,2)

return 1 ret c(0,1) + c(1,1) ret c(0,1)+c(1,1) return 1

c(0,1) c(1,1) c(0,1) c(1,1)

return 1 return 1 return 1 return 1

The final answer is the sum of the base cases

[ CS1020E AY1617S1 Lecture 8 ]
23
Example: Fibonacci Numbers
Rabbits give birth monthly once they are 3 months old and they always
conceive a single male-female pair.
Given a pair of male-female rabbits, assuming rabbits never die, how
many pairs of rabbits are there after n months?

[ CS1020E AY1617S1 Lecture 8 ]

24
The Fibonacci Series
 Rabbit(N)= # pairs of rabbit at Nth month
 All rabbit pairs in the previous month (N−1)th month stay
 Rabbits never die
 Additionally, new rabbit pairs = the total rabbit pairs two
months ago (N−2)th month
 Rabbits give birth at the 3rd month

 Hence:
 Rabbit(N) = Rabbit(N–1) + Rabbit(N–2)

 Special cases:
 Rabbit(1) = 1 One pair in the 1st month
 Rabbit(2) = 1 Still one pair in the 2nd month

 Rabbit(N) is the famous Fibonacci(N)

[ CS1020E AY1617S1 Lecture 8 ]
25
Fibonacci Number: Implementation
Base Cases:
long fibo(int n) {
fibo(1) = 1
if (n <= 2) fibo(2) = 1
return 1;
else
return fibo(n-1) + fibo(n-2);
}

Recursive Case:
fibo(n) = fibo(n–1) + fibo(n–2)

[ CS1020E AY1617S1 Lecture 8 ]

26
Execution Trace: Fibonacci
fib(6)

fib(5) fib(4)

fib(4) fib(3) fib(3) fib(2)

fib(3) fib(2) fib(2) fib(1) fib(2) fib(1)

fib(2) fib(1)

 Many duplicate calls

 The same computations are done over and over again!
[ CS1020E AY1617S1 Lecture 8 ]
27
Fibonacci Number: Iterative Solution
long fibo(int n) {
long cur, prev1 = 1, prev2 = 1, j;

if (n <= 2)
return 1;
else
for (j = 3; j <= n; j++) {
cur = prev1 + prev2;
prev2 = prev1;
prev1 = cur;
}
return cur; Iterative
} Version

 How much time do we need to calculate a particular

fibonacci number?
[ CS1020E AY1617S1 Lecture 8 ]
28
Example: Searching in Sorted Array
 Given a sorted array a of n elements and x,
determine if x is in a
a = 1 5 6 13 14 19 21 24 32

x = 15

 How do you reduce the number of checking?

 Idea: Narrow the search space by half at every
iteration until a single element is reached

[ CS1020E AY1617S1 Lecture 8 ]

29
Binary Search
int binarySearch(int a[], int x, int low, int high) {
if (low > high) // Base Case 1: item not found
return -1;

int mid = (low+high) / 2;

if (x > a[mid])
return binarySearch(a, x, mid+1, high);
else if (x < a[mid])
return binarySearch(a, x, low, mid–1);
else
return mid; // Base Case 2: item found
}

[ CS1020E AY1617S1 Lecture 8 ]

30
 Example: Find all Permutations of a String
 Given a word, say east, the program should print all 24
permutations (anagrams), including eats, etas, teas, and non-
words like tsae

 One idea to generate all permutations (other ways exist)

 Given east, we place the first character, i.e. e, in front of all 6
permutations of the other 3 characters ast — ast, ats, sat, sta, tas,
and tsa — to arrive at east, eats, esat, esta, etas, and etsa, then
 We place the second character, i.e. a, in front of all 6 permutations of
est, then
 We do the same for characters s and t
 Thus, there will be 4 (the size of the word) recursive calls to display
all permutations of a four-letter word

 Of course, when we’re going through the permutations of 3-

character string, e.g. ast, we would follow the same procedure
[ CS1020E AY1617S1 Lecture 8 ]
32
Example: Find all Permutations of a String
void permuteString(string beginningString,
string endingString) {
if (endingString.length() <= 1)
cout << beginningString << endingString << endl;
else
for (int i = 0; i < endingString.length(); i++) {
string newString = endingString.substr(0, i) +
endingString.substr(i+1);
permuteString(beginningString + endingString[i],
newString);
}
}

 Start by calling permutateString("", "east");

[ CS1020E AY1617S1 Lecture 8 ]

33
Summary
 Recursion is not just a way of programming, it
is also a powerful approach to problem
solving and formulating a solution

 A recursive function has base cases and

recursive cases

 Relationship between recursion and stack

 Watch out for duplicate computations!

[ CS1020E AY1617S1 Lecture 8 ]
34
VisuAlgo Recursion Tree Visualization
 http://visualgo.net/recursion
 Accepts any
valid (JavaScript)
recursive function
with starting
input parameter
 Green vertices:
base cases
 Blue vertices:
Repeated cases
 Red text:
Return values
[ CS1020E AY1617S1 Lecture 8 ]
35