Data Structure and Algorithms [CO2003]

Chapter 3 - Recursion

Lecturer: Vuong Ba Thinh

Contact: vbthinh@hcmut.edu.vn

Faculty of Computer Science and Engineering

Hochiminh city University of Technology
Contents

1. Recursion and the basic components of recursive algorithms

2. Properties of recursion

3. Designing recursive algorithms

4. Recursion and backtracking

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 1 / 38
Outcomes

ˆ L.O.8.1 - Describe the basic components of recursive algorithms

(functions).
ˆ L.O.8.2 - Draw trees to illustrate callings and the value of
parameters passed to them for recursive algorithms.
ˆ L.O.8.3 - Give examples for recursive functions written in C/C++.
ˆ L.O.8.5 - Develop experiment (program) to compare the recursive
and the iterative approach.
ˆ L.O.8.6 - Give examples to relate recursion to backtracking
technique.

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 2 / 38
Recursion and the basic
components of recursive
algorithms
Recursion

Denition
Recursion is a repetitive process in which an algorithm calls itself.

ˆ Direct : A → A
ˆ Indirect : A → B → A

Example
Factorial "
1 if n = 0
F actorial(n) =
n × (n − 1) × (n − 2) × ... × 3 × 2 × 1 if n > 0

Using recursion: "

1 if n = 0
F actorial(n) =
n × F actorial(n − 1) if n > 0

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 3 / 38
Basic components of recursive algorithms

Two main components of a Recursive Algorithm

1. Base case (i.e. stopping case)
2. General case (i.e. recursive case)

Example
Factorial "
1 if n = 0 base case
F actorial(n) =
n × F actorial(n − 1) if n > 0 general case

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 4 / 38
Recursion

Figure 1: Factorial (3) Recursively (source: Data Structure - A pseudocode

Approach with C++)

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 5 / 38
Recursion

Factorial: Iterative Solution

Algorithm iterativeFactorial(n)
Calculates the factorial of a number using a loop.
Pre: n is the number to be raised factorially
Post: n! is returned - result in factoN

i=1
factoN = 1
while i <= n do
factoN = factoN * i
i=i+1
end
return factoN
End iterativeFactorial

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 6 / 38
Recursion

Factorial: Recursive Solution

Algorithm recursiveFactorial(n)
Calculates the factorial of a number using a recursion.
Pre: n is the number to be raised factorially
Post: n! is returned

if n = 0 then
return 1
else
return n * recursiveFactorial(n-1)
end
End recursiveFactorial

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 7 / 38
Recursion

Figure 2: Calling a Recursive Algorithm (source: Data Structure - A

pseudocode Approach with C++)
Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 8 / 38
Properties of recursion
Properties of all recursive algorithms

ˆ A recursive algorithm solves the large problem by using its solution

to a simpler sub-problem

ˆ Eventually the sub-problem is simple enough that it can be solved

without applying the algorithm to it recursively.
→ This is called the base case.

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 9 / 38
Designing recursive algorithms
The Design Methodology

Every recursive call must either solve a part of the problem or reduce the
size of the problem.

Rules for designing a recursive algorithm

1. Determine the base case (stopping case).
2. Then determine the general case (recursive case).
3. Combine the base case and the general cases into an algorithm.

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 10 / 38
Limitations of Recursion

ˆ A recursive algorithm generally runs more slowly than its

nonrecursive implementation.

ˆ BUT, the recursive solution shorter and more understandable.

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 11 / 38
Print List in Reverse

93 19 8 26

26 8 19 93

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 12 / 38
Print List in Reverse

93 19 8 26

26 8 19 93

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 13 / 38
Print List in Reverse

Algorithm printReverse(list)
Prints a linked list in reverse.
Pre: list has been built
Post: list printed in reverse

if list is null then

return
end
printReverse (list -> next)
print (list -> data)
End printReverse

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 14 / 38
Greatest Common Divisor

Denition
" a if b = 0
gcd(a, b) = b if a = 0
gcd(b, a mod b) otherwise
Example
gcd(12, 18) = 6
gcd(5, 20) = 5

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 15 / 38
Greatest Common Divisor

Algorithm gcd(a, b)
Calculates greatest common divisor using the Euclidean algorithm.
Pre: a and b are integers
Post: greatest common divisor returned

if b = 0 then
return a
end
if a = 0 then
return b
end
return gcd(b, a mod b)
End gcd

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 16 / 38
Fibonacci Numbers

Denition
" 0 if n = 0
F ibonacci(n) = 1 if n = 1
F ibonacci(n − 1) + F ibonacci(n − 2) otherwise

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 17 / 38
Fibonacci Numbers

Fib(n)

Fib(n-1) + Fib(n-2)

Fib(n-2) + Fib(n-3) + Fib(n-4)

Fib(n-3) + Fib(n-4)

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 18 / 38
Fibonacci Numbers

Fib(4) 3

Fib(3) 2 + Fib(2) 1

Fib(2) 1 + Fib(1) 1 + Fib(0) 0

Fib(1) 1 + Fib(0) 0

Result
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 19 / 38
Fibonacci Numbers

Algorithm b(n)
Calculates the nth Fibonacci number.
Pre: n is postive integer
Post: the nth Fibonnacci number returned

if n = 0 or n = 1 then
return n
end
return b(n-1) + b(n-2)
End b

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 20 / 38
Fibonacci Numbers

No Calls Time No Calls Time

1 1 < 1 sec. 11 287 < 1 sec.
2 3 < 1 sec. 12 465 < 1 sec.
3 5 < 1 sec. 13 753 < 1 sec.
4 9 < 1 sec. 14 1,219 < 1 sec.
5 15 < 1 sec. 15 1,973 < 1 sec.
6 25 < 1 sec. 20 21,891 < 1 sec.
7 41 < 1 sec. 25 242,785 1 sec.
8 67 < 1 sec. 30 2,692,573 7 sec.
9 109 < 1 sec. 35 29,860,703 1 min.
10 177 < 1 sec. 40 331,160,281 13 min.

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 21 / 38
The Towers of Hanoi

Move disks from Source to Destination using Auxiliary:

1. Only one disk could be moved at a time.

2. A larger disk must never be stacked above a smaller one.
3. Only one auxiliary needle could be used for the intermediate storage
of disks.

1
2
3
Source Auxiliary Destination
Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 22 / 38
The Towers of Hanoi

2
3 1
Source Auxiliary Destination

Moved disc from pole 1 to pole 3.

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 23 / 38
The Towers of Hanoi

3 2 1
Source Auxiliary Destination

Moved disc from pole 1 to pole 2.

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 24 / 38
The Towers of Hanoi

1
3 2
Source Auxiliary Destination

Moved disc from pole 3 to pole 2.

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 25 / 38
The Towers of Hanoi

1
2 3
Source Auxiliary Destination

Moved disc from pole 1 to pole 3.

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 26 / 38
The Towers of Hanoi

1 2 3
Source Auxiliary Destination

Moved disc from pole 2 to pole 1.

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 27 / 38
The Towers of Hanoi

2
1 3
Source Auxiliary Destination

Moved disc from pole 2 to pole 3.

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 28 / 38
The Towers of Hanoi

1
2
3
Source Auxiliary Destination

Moved disc from pole 1 to pole 3.

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 29 / 38
The Towers of Hanoi

move(3,
A, C, B)

move(2, move(1, move(2,

A, B, C) A, C, B) B, C, A)

A -> C

move(1, move(1, move(1, move(1, move(1, move(1,

A, C, B) A, B, C) C, B, A) B, A, C) B, C, A) A, C, B)

A -> C A -> B C -> B B -> A B -> C A -> C

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 30 / 38
The Towers of Hanoi : General

move(n, A, C, B)

move(n-1, A, B, C) move(1, A, C, B) move(n-1, B, C, A)

Complexity
T (n) = 1 + 2T (n − 1)

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 31 / 38
The Towers of Hanoi

Complexity
T (n) = 1 + 2T (n − 1)
=> T (n) = 1 + 2 + 22 + ... + 2n−1
=> T (n) = 2n − 1
=> T (n) = O(2n )

ˆ With 64 disks, total number of moves:

264 − 1 ≈ 24 × 260 ≈ 24 × 1018 = 1.6 × 1019
ˆ If one move takes 1s, 264 moves take about 5 × 1011 years (500
billions years).

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 32 / 38
The Towers of Hanoi

Algorithm move(val disks <integer>, val source <character>, val

destination <character>, val auxiliary <character>)
Move disks from source to destination.
Pre: disks is the number of disks to be moved
Post: steps for moves printed
print("Towers: ", disks, source, destination, auxiliary)
if disks = 1 then
print ("Move from", source, "to", destination)
else
move(disks - 1, source, auxiliary, destination)
move(1, source, destination, auxiliary)
move(disks - 1, auxiliary, destination, source)
end
return
End move
Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 33 / 38
Recursion and backtracking
Backtracking

Denition
A process to go back to previous steps to try unexplored alternatives.

Figure 3: Goal seeking

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 34 / 38
Eight Queens Problem

Place eight queens on the chess board in such a way that no queen can
capture another.

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 35 / 38
Eight Queens Problem

Algorithm putQueen(ref board <array>, val r <integer>)

Place remaining queens safely from a row of a chess board.

Pre: board is nxn array representing a chess board

r is the row to place queens onwards

Post: all the remaining queens are safely placed on the board; or
backtracking to the previous rows is required

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 36 / 38
Eight Queens Problem

for every column c on the same row r do

if cell r,c is safe then
place the next queen in cell r,c
if r < n-1 then
putQueen (board, r + 1)
else
output successful placement
end
remove the queen from cell r,c
end
end
return
End putQueen

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 37 / 38
Eight Queens Problem

Lecturer: Vuong Ba Thinh Contact: vbthinh@hcmut.edu.vn Data Structure and Algorithms [CO2003] 38 / 38