Recursion

Chapter 6 (Malik)
Chapter 2 (Shaffer)
What is Recursion? 2
 3

Recursion is the process of

using oneself
as part of one's own definition
 4

Droste Effect
(Recursion in Art)
 5

Nevit Dilmen. [Link]

 6

Matryoshka Dolls
Fanghong. [Link]
 7

BrokenSphere. [Link]
 8

Sierpiński Triangle
(Recursion in Math)
 9

Romanesco Broccoli
(Recursion in Nature)
 10

Angelica Flowerhead
(Recursion in Nature)
Recursive Function 11

• A function that calls itself is considered a recursive function

• Conceptually, think of recursion as a loop
• Just like a loop, must have some way to stop the recursion
• Depth of recursion is the number of calls to a recursive function
• Excludes the primary call (the first one to start the recursion)
Recursion Properties 12

• Without proper care, recursion will continue infinitely

• Requires three properties to ensure termination
1. Base case(s)
2. Recursive case(s)
3. Progress from a recursive case to a base case
Using Iteration to Create Recursion 13
 14

How can we compute

the sum of positive integers
between 0 and a given limit?
 15

unsigned sum(unsigned limit) {

unsigned s = 0;
while (limit > 0) {
s += limit;
limit--;
}
return s;
}
Converting Iteration to Recursion 16

• The iterative solution explicitly gives us the 3 requirements for

writing a recursive solution
1. Base case(s)
2. Recursive case(s)
3. Progress from a recursive case to a base case
 17
unsigned sumRec(unsigned limit) {
unsigned sum(unsigned limit) {
// base case
unsigned s = 0;
if (limit == 0) {
while (limit > 0) {
// ???
s += limit;
}
limit--;
}
// recursive case
return s;
// ???
}
}
 18
unsigned sumRec(unsigned limit) {
unsigned sum(unsigned limit) {
// base case
unsigned s = 0;
if (limit == 0) {
while (limit > 0) {
return 0;
s += limit;
}
limit--;
}
// recursive case
return s;
// ???
}
}
 19
unsigned sumRec(unsigned limit) {
unsigned sum(unsigned limit) { // base case
unsigned s = 0; if (limit == 0) {
while (limit > 0) { return 0;
s += limit; }
limit--;
} // recursive case
return s; unsigned s = sumRec(limit - 1);
} return s + limit;
}
Function Call Recursive Calculations
sumRec(0) = 0
20
Function Call Recursive Calculations
sumRec(0) = 0
sumRec(1) 1 + sumRec(0)
= 1 + 0
21
= 1
Function Call Recursive Calculations
sumRec(0) = 0
sumRec(1) 1 + sumRec(0)
= 1 + 0
22
= 1
sumRec(2) 2 + sumRec(1)
= 2 + 1 + sumRec(0)
= 2 + 1 + 0
= 3
Function Call Recursive Calculations
sumRec(0) = 0
sumRec(1) 1 + sumRec(0)
= 1 + 0
23
= 1
sumRec(2) 2 + sumRec(1)
= 2 + 1 + sumRec(0)
= 2 + 1 + 0
= 3
sumRec(3) 3 + sumRec(2)
= 3 + 2 + sumRec(1)
= 3 + 2 + 1 + sumRec(0)
= 3 + 2 + 1 + 0
= 6
Function Call Recursive Calculations
sumRec(0) = 0
sumRec(1) 1 + sumRec(0)
= 1 + 0
24
= 1
sumRec(2) 2 + sumRec(1)
= 2 + 1 + sumRec(0)
= 2 + 1 + 0
= 3
sumRec(3) 3 + sumRec(2)
= 3 + 2 + sumRec(1)
= 3 + 2 + 1 + sumRec(0)
= 3 + 2 + 1 + 0
= 6
sumRec(4) 4 + sumRec(3)
= 4 + 3 + sumRec(2)
= 4 + 3 + 2 + sumRec(1)
= 4 + 3 + 2 + 1 + sumRec(0)
= 4 + 3 + 2 + 1 + 0
= 10
sumRec(4)
25
sumRec(3)
sumRec(5)

sumRec(2)

sumRec(1)

sumRec(0)
 26

Depth of recursion?
Time complexity?
Recursive Mathematical Definitions 27
Math and Recursion 28

• Many mathematical problems are defined recursively

• Therefore, it’s easier to write a recursive function to solve them
• Can still write iterative solutions, but it’s not as “natural”
Fibonacci Numbers 29

• A sequence of numbers that behave

according to a specific pattern
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .
Fibonacci Numbers 30

• 𝐹0 = 0
• 𝐹1 = 1
• 𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2 for all 𝑛 ≥ 2
Fibonacci Numbers 31

0 𝑛=0
• 𝐹 𝑛 =ቐ 1 𝑛=1
𝐹 𝑛 − 1 + 𝐹(𝑛 − 2) 𝑛≥2
 32

How do we calculate
the 5th Fibonacci number?
 0 𝑛=0 33
𝐹 𝑛 =ቐ 1 𝑛=1
𝐹 𝑛 − 1 + 𝐹(𝑛 − 2) 𝑛≥2

Function Call Recursive Calculations Result

F(5) F(4) + F(3)
 0 𝑛=0 34
𝐹 𝑛 =ቐ 1 𝑛=1
𝐹 𝑛 − 1 + 𝐹(𝑛 − 2) 𝑛≥2

Function Call Recursive Calculations Result

F(5) F(4) + F(3)
F(4) F(3) + F(2)
F(3) F(2) + F(1)
 0 𝑛=0 35
𝐹 𝑛 =ቐ 1 𝑛=1
𝐹 𝑛 − 1 + 𝐹(𝑛 − 2) 𝑛≥2

Function Call Recursive Calculations Result

F(5) F(4) + F(3)
F(4) F(3) + F(2)
F(3) F(2) + F(1)
F(2) F(1) + F(0)
F(1) 1
 0 𝑛=0 36
𝐹 𝑛 =ቐ 1 𝑛=1
𝐹 𝑛 − 1 + 𝐹(𝑛 − 2) 𝑛≥2

Function Call Recursive Calculations Result

F(5) F(4) + F(3)
F(4) F(3) + F(2)
F(3) F(2) + F(1)
F(2) F(1) + F(0)
F(1) 1
F(0) 0
 0 𝑛=0 37
𝐹 𝑛 =ቐ 1 𝑛=1
𝐹 𝑛 − 1 + 𝐹(𝑛 − 2) 𝑛≥2

Function Call Recursive Calculations Result

F(5) F(4) + F(3)
F(4) F(3) + F(2)
F(3) F(2) + F(1)
F(2) F(1) + F(0)
F(1) 1 1
F(0) 0 0
 0 𝑛=0 38
𝐹 𝑛 =ቐ 1 𝑛=1
𝐹 𝑛 − 1 + 𝐹(𝑛 − 2) 𝑛≥2

Function Call Recursive Calculations Result

F(5) F(4) + F(3)
F(4) F(3) + F(2)
F(3) F(2) + F(1)
F(2) F(1) + F(0) 1 + 0 = 1
F(1) 1 1
F(0) 0 0
 0 𝑛=0 39
𝐹 𝑛 =ቐ 1 𝑛=1
𝐹 𝑛 − 1 + 𝐹(𝑛 − 2) 𝑛≥2

Function Call Recursive Calculations Result

F(5) F(4) + F(3)
F(4) F(3) + F(2)
F(3) F(2) + F(1) 1 + 1 = 2
F(2) F(1) + F(0) 1 + 0 = 1
F(1) 1 1
F(0) 0 0
 0 𝑛=0 40
𝐹 𝑛 =ቐ 1 𝑛=1
𝐹 𝑛 − 1 + 𝐹(𝑛 − 2) 𝑛≥2

Function Call Recursive Calculations Result

F(5) F(4) + F(3)
F(4) F(3) + F(2) 2 + 1 = 3
F(3) F(2) + F(1) 1 + 1 = 2
F(2) F(1) + F(0) 1 + 0 = 1
F(1) 1 1
F(0) 0 0
 0 𝑛=0 41
𝐹 𝑛 =ቐ 1 𝑛=1
𝐹 𝑛 − 1 + 𝐹(𝑛 − 2) 𝑛≥2

Function Call Recursive Calculations Result

F(5) F(4) + F(3) 3 + 2 = 5
F(4) F(3) + F(2) 2 + 1 = 3
F(3) F(2) + F(1) 1 + 1 = 2
F(2) F(1) + F(0) 1 + 0 = 1
F(1) 1 1
F(0) 0 0
 42

Recursion is all about

breaking BIG problems
into smaller problems!
 0 𝑛=0 43
𝐹 𝑛 =ቐ 1 𝑛=1
𝐹 𝑛 − 1 + 𝐹(𝑛 − 2) 𝑛≥2

Function Call Recursive Calculations Result

F(5) F(4) + F(3) 3 + 2 = 5
F(4) F(3) + F(2) 2 + 1 = 3
F(3) F(2) + F(1) 1 + 1 = 2
F(2) F(1) + F(0) 1 + 0 = 1
F(1) 1 1
F(0) 0 0
 unsigned fib(unsigned n) {
44
// base case 1
if (n == 0) {
return 0;
}
0 𝑛=0 // base case 2
𝐹 𝑛 =ቐ 1 𝑛=1 else if (n == 1) {
𝐹 𝑛 − 1 + 𝐹(𝑛 − 2) 𝑛≥2 return 1;
}

// recursive case
return fib(n - 1) + fib(n - 2);
}
 45
unsigned fib(unsigned n) {
// base cases (combined)
if (n <= 1) {
0 𝑛=0 return n;
𝐹 𝑛 =ቐ 1 𝑛=1 }
𝐹 𝑛 − 1 + 𝐹(𝑛 − 2) 𝑛≥2
// recursive case
return fib(n - 1) + fib(n - 2);
}
 46

Depth of recursion?
Time complexity?

Answer is 𝒪 2𝑛 but requires

advanced techniques to derive!
Side Note 47

• There is a closed-form solution for Fibonacci numbers

𝜑𝑛 − 𝜓𝑛
𝐹 𝑛 =
5

1+ 5
𝜑=
2

1− 5
𝜓=
2
More Recursive Problems 48
Finding the Maximum 49

• Suppose you are given an array of size 𝑛

• How can we find the largest element in the array?
Iterative solution is simple! 50

8 3 7 12 0 -4
0 1 2 3 4 5

𝑛=6
 51
template <typename T>
T findMax(const T arr[], const int SIZE) {
T mx = arr[0];

for (int i = 1; i < SIZE; i++) {

if (arr[i] > mx) {
mx = arr[i];
}
}

return mx;
}

Time complexity?
What about a recursive solution?
52

8 3 7 12 0 -4
0 1 2 3 4 5

𝑛=6
 53
template <typename T>
T findMax(const T arr[], const int SIZE) { template <typename T>
T mx = arr[0]; T findMaxRec(const T arr[], const int SIZE,
T mx, int i = 1) {
for (int i = 1; i < SIZE; i++) { // base case
if (arr[i] > mx) { if (i == SIZE) {
mx = arr[i]; // ???
} }
}
// recursive case
return mx; // ???
} }
 54
template <typename T>
T findMax(const T arr[], const int SIZE) { template <typename T>
T mx = arr[0]; T findMaxRec(const T arr[], const int SIZE,
T mx, int i = 1) {
for (int i = 1; i < SIZE; i++) { // base case
if (arr[i] > mx) { if (i == SIZE) {
mx = arr[i]; return mx;
} }
}
// recursive case
return mx; // ???
} }
 55
template <typename T>
template <typename T> T findMaxRec(const T arr[], const int SIZE,
T findMax(const T arr[], const int SIZE) { T mx, int i = 1) {
T mx = arr[0]; // base case
if (i == SIZE) {
for (int i = 1; i < SIZE; i++) { return mx;
if (arr[i] > mx) { }
mx = arr[i];
} // recursive case
} if (arr[i] > mx) {
mx = arr[i];
return mx; }
} return findMaxRec(arr, SIZE, mx, i + 1);
}
 56

Depth of recursion?
Time complexity?
A different recursive solution?57

8 3 7 12 0 -4
0 1 2 3 4 5

𝑛=6
 YES!
58
Remember: recursion is all about breaking
big problems into smaller ones

8 3 7 12 0 -4
0 1 2 3 4 5

𝑛=6
 59

8 3 7 12 0 -4
0 1 2 3 4 5

𝑛=6
② Compare it against the head
① Figure out the maximum of the tail
60

8 3 7 12 0 -4
0 1 2 3 4 5

𝑛=6
② Compare it against the head
① Figure out the maximum of the
61 tail

8 3 7 12 0 -4
0 1 2 3 4 5

𝑛=5
② Compare it against the head
① Figure out the maximum of 62
the tail

8 3 7 12 0 -4
0 1 2 3 4 5

𝑛=4
② Compare it against the head
① Figure out the maximum of 63
the tail

8 3 7 12 0 -4
0 1 2 3 4 5

𝑛=3
② Compare it against the head
① Figure out the maximum of 64
the tail

8 3 7 12 0 -4
0 1 2 3 4 5

𝑛=2
 Base case! 65
Now start unwinding . . .

8 3 7 12 0 -4
0 1 2 3 4 5

𝑛=1
Tower of Hanoi 66

• There are 3 rods on a board

• On rod #1, there are 𝑛 disks of different sizes
• Biggest is at the bottom, then decreases in size
• The goal is to move all 𝑛 disks from rod #1 to rod #3
• Rules
1. Only one disk can be moved at a time
2. The removed disk must be placed on one of the rods
3. A larger disk cannot be placed on top of a smaller disk
 67

Can we solve the

Tower of Hanoi
problem recursively?
Solving the 𝑛 = 0 Case 68

Rod 1 Rod 2 Rod 3

Moves: 0
Solving the 𝑛 = 1 Case 69

Disk 1

Rod 1 Rod 2 Rod 3

Moves: 1
Solving the 𝑛 = 2 Case 70

Disk 1
Disk 2

Rod 1 Rod 2 Rod 3

Moves: 0
Solving the 𝑛 = 2 Case 71

Disk 1
Disk 2

Rod 1 Rod 2 Rod 3

Moves: 0
Solving the 𝑛 = 2 Case 72

Disk 2 Disk 1

Rod 1 Rod 2 Rod 3

Moves: 1
Solving the 𝑛 = 2 Case 73

Disk 2 Disk 1

Rod 1 Rod 2 Rod 3

Moves: 1
Solving the 𝑛 = 2 Case 74

Disk 1 Disk 2

Rod 1 Rod 2 Rod 3

Moves: 2
Solving the 𝑛 = 2 Case 75

Disk 1 Disk 2

Rod 1 Rod 2 Rod 3

Moves: 2
Solving the 𝑛 = 2 Case 76

Disk 1

Disk 2

Rod 1 Rod 2 Rod 3

Moves: 3
Solving the 𝑛 = 3 Case 77

Disk 1
How can this problem be
Disk 2
broken into a smaller problem?
Disk 3

Rod 1 Rod 2 Rod 3

Moves: 0
Solving the 𝑛 = 3 Case 78

Disk 1
Disk 3 Disk 2

Rod 1 Rod 2 Rod 3

Moves: x
Solving the 𝑛 = 3 Case 79

Disk 1
Disk 3 Disk 2

Rod 1 Rod 2 Rod 3

Moves: x
Solving the 𝑛 = 3 Case 80

Disk 1
Disk 2 Disk 3

Rod 1 Rod 2 Rod 3

Moves: x + 1
 81

How can we make

disks 1 and 2 be
placed on rod #2?
Solving the 𝑛 = 2 Case 82

Disk 1
Disk 2

Rod 1 Rod 2 Rod 3

Moves: 0
Solving the 𝑛 = 2 Case [Modified] 83

Flip rods #2 and #3!

Disk 1
Disk 2

Rod 1 Rod 3 Rod 2

Moves: 0
Solving the 𝑛 = 2 Case [Modified] 84

Disk 1

Disk 2

Rod 1 Rod 3 Rod 2

Moves: 3
Solving the 𝑛 = 3 Case 85

Disk 1
Disk 2 Disk 3

Rod 1 Rod 2 Rod 3

Moves: 3 + 1 = 4
 86

How to get disks 1 and 2 to rod #3?

Solving the 𝑛 = 2 Case [Modified, Again] 87

Flip rods #1 and #2!

Disk 1
Disk 2

Rod 2 Rod 1 Rod 3

Moves: 0
Solving the 𝑛 = 2 Case [Modified, Again] 88

Disk 1

Disk 2

Rod 2 Rod 1 Rod 3

Moves: 3
Solving the 𝑛 = 3 Case 89

Disk 1
Disk 2
Disk 3

Rod 1 Rod 2 Rod 3

Moves: 3 + 1 + 3 = 7
Recursive Data Types 90
Chapter 6
Recursive Data Types 91

• Recursion is not limited to functions

• Data types (structures) can be defined recursively as well
• Recursive types lend themselves naturally to recursion
• Linked list is a prime example of this
Linked List Operations 92

• Most algorithms used loops to traverse through the list

• Possible to use recursion instead to do the traversal
• Key idea: add a node pointer as a parameter to traverse as we do
the recursion
 93

Let’s try appending recursively!

 94

How about printing recursively?

 95

Can we print in reverse?

 96

Is there another recursive

definition for a linked list?
Recursion Performance 97
Recursion 98

• Many problems can be solved by subdividing into smaller problem

instances
• Hence, many solutions can be developed easily with recursion
• Most mathematical definitions are also recursively defined
• But, most recursive solutions are inefficient due to function call
overhead
• Requires fine-tuning and optimizations to overcome these overheads
Iteration 99

• Simple tasks can be done easily with loops

• Generally more efficient than recursion since there is no function
call overhead
• But, some iterative solutions are more complicated than their
recursive counterparts
• Especially for problems that lend themselves to recursion naturally
Activation Records 100

• When a function is called, the program creates an activation

record for it
• A structure that stores information about the function
• The address of the function
• A pointer to its caller (the function that called it)
• Local variable information
• Activation records require memory space
 Activation Record for main()
Function Address: 0x00A04100
101
Caller Address: nullptr
int f(int i) { Local Variables:
int j = i + 5; {x, 9, 0x01BC6402}
return j;
}

int main() {
int x = 9;
cout << f(x) << endl;
return 0; Activation Record for f(int)
} Function Address: 0x00A04230
Caller Address: 0x00A04100
Local Variables:
{i, 9, 0x01BC64A0}
{j, 14, 0x01BC64A4}
 102

How about for recursion?

 Activation Record for main()
Function Address: 0x00A04100

unsigned sumRec(unsigned limit) {

Caller Address: nullptr
Local Variables: N/A
103
// base case
if (limit == 0) {
return 0; Activation Record for sumRec(unsigned)
} Function Address: 0x00A04230
Caller Address: 0x00A04100
// recursive case
Local Variables:
unsigned s = sumRec(limit - 1); {limit, 3, 0x01BC64A0}
return s + limit; {s, ?, 0x01BC64A4}
}

int main() {
Activation Record for sumRec(unsigned)
cout << sumRec(3) << endl;
Function Address: 0x00A04260
return 0;
Caller Address: 0x00A04230
}
Local Variables:
{limit, 2, 0x01BC64B0}
{s, ?, 0x01BC64B4}
Activation Record for main()
Function Address: 0x00A04100
Caller Address: nullptr
Local Variables: N/A
104
Activation Record for sumRec(unsigned)
Function Address: 0x00A04290
Caller Address: 0x00A04260
Activation Record for sumRec(unsigned)
Function Address: 0x00A04230 Local Variables:
Caller Address: 0x00A04100 {limit, 1, 0x01BC64C0}
{s, ?, 0x01BC64C4}
Local Variables:
{limit, 3, 0x01BC64A0}
{s, ?, 0x01BC64A4}
Activation Record for sumRec(unsigned)
Function Address: 0x00A042C0
Activation Record for sumRec(unsigned) Caller Address: 0x00A04290
Function Address: 0x00A04260 Local Variables:
Caller Address: 0x00A04230 {limit, 0, 0x01BC64D0}
Local Variables: {s, ?, 0x01BC64D4}
{limit, 2, 0x01BC64B0}
{s, ?, 0x01BC64B4}
Activation Record for main()
Function Address: 0x00A04100
Caller Address: nullptr
Local Variables: N/A
105
Activation Record for sumRec(unsigned)
Function Address: 0x00A04290
Caller Address: 0x00A04260
Activation Record for sumRec(unsigned)
Function Address: 0x00A04230 Local Variables:
Caller Address: 0x00A04100 {limit, 1, 0x01BC64C0}
{s, 0,
?, 0x01BC64C4}
Local Variables:
{limit, 3, 0x01BC64A0}
{s, 3,
?, 0x01BC64A4}
Activation Record for sumRec(unsigned)
Function Address: 0x00A042C0
Activation Record for sumRec(unsigned) Caller Address: 0x00A04290
Function Address: 0x00A04260 Local Variables:
Caller Address: 0x00A04230 {limit, 0, 0x01BC64D0}
Local Variables: {s, ?, 0x01BC64D4}
{limit, 2, 0x01BC64B0}
{s, 1,
?, 0x01BC64B4}
Recursion and Function Call Overhead 106

• Recursion suffers from function call overhead

• Every time the function is called recursively, another activation
record has to be made
• Each activation record takes up memory space
• If the depth of recursion is too large, you get a memory overflow!

Can we overcome this?

Tail Recursion 107

• Many programming languages can optimize recursion to avoid the

problem
• Tail recursion is a technique where only 1 activation record is used
for all recursive calls
• Requirement
• Refactor code to make the recursive call the last thing it performs
• Hence, it can just override the values in the activation record for
the next call
 unsigned sumRecTail(unsigned limit, unsigned result = 0) {
// base case
if (limit == 0) {
return result;
108
}

// recursive case
return sumRecTail(limit - 1, result + limit);
}

int main() {
cout << sumRecTail(3) << endl;
return 0;
}

Activation Record for sumRecTail(unsigned, unsigned)

Activation Record for main() Function Address: 0x00A04230
Function Address: 0x00A04100 Caller Address: 0x00A04100
Caller Address: nullptr Local Variables:
Local Variables: N/A {limit, 3, 0x01BC64A0}
{result, 0, 0x01BC64A4}
 unsigned sumRecTail(unsigned limit, unsigned result = 0) {
// base case
if (limit == 0) {
return result;
109
}

// recursive case
return sumRecTail(limit - 1, result + limit);
}

int main() {
cout << sumRecTail(3) << endl;
return 0;
}

Activation Record for sumRecTail(unsigned, unsigned)

Activation Record for main() Function Address: 0x00A04230
Function Address: 0x00A04100 Caller Address: 0x00A04100
Caller Address: nullptr Local Variables:
Local Variables: N/A {limit, 2, 0x01BC64A0}
{result, 3, 0x01BC64A4}
 unsigned sumRecTail(unsigned limit, unsigned result = 0) {
// base case
if (limit == 0) {
return result;
110
}

// recursive case
return sumRecTail(limit - 1, result + limit);
}

int main() {
cout << sumRecTail(3) << endl;
return 0;
}

Activation Record for sumRecTail(unsigned, unsigned)

Activation Record for main() Function Address: 0x00A04230
Function Address: 0x00A04100 Caller Address: 0x00A04100
Caller Address: nullptr Local Variables:
Local Variables: N/A {limit, 1, 0x01BC64A0}
{result, 5, 0x01BC64A4}
 unsigned sumRecTail(unsigned limit, unsigned result = 0) {
// base case
if (limit == 0) {
return result;
111
}

// recursive case
return sumRecTail(limit - 1, result + limit);
}

int main() {
cout << sumRecTail(3) << endl;
return 0;
}

Activation Record for sumRecTail(unsigned, unsigned)

Activation Record for main() Function Address: 0x00A04230
Function Address: 0x00A04100 Caller Address: 0x00A04100
Caller Address: nullptr Local Variables:
Local Variables: N/A {limit, 0, 0x01BC64A0}
{result, 6, 0x01BC64A4}
Tail Recursion in C++ 112

• Most C++ compilers will support tail recursion optimization

• However, it sometimes requires the –O2 flag to be turned on
• Typographic note, that’s a capital Oh, not a zero
• For simple recursive functions, compilers can even create the tail
recursion by itself without you refactoring