Fundamentals of

Recursion
 Lecture Flow

1) Pre-requisites
2) Problem definitions
3) Time and Space Complexity of Data Structure
4) Check point
5) Recognizing in Questions
6) Things to Pay Attention(common pitfalls)
7) Practice questions
8) Resources
9) Quote of the day
 Pre-requisites
● Understanding iterative program flow
● Functions, local variables and global variables
● Stack data structures
 Real Life Example

Imagine you are in a long queue and the reception asks you how many
people there are in the line. How do you count the number of people in
the queue?
Brainstorm
● Let’s assume each person in the queue
○ Can increment numbers by 1
○ Can request other people
● What if I asked the person behind me “how many people there are” and
whatever their response is, I can do plus 1 and inform the reception? And
● What if the person I asked, asks the person behind them “how many people
there are” and whatever they get, they do plus 1 and inform me?
•
•
•

5
 1 Asking and Aggregating steps
How many
people are 2
How many 4
there? 3
How many people behind
people you including 5
reception behind you yourself? Only Me
Let me
including
check…
yourself?
2 + 1= 3
7

6
There
are 2
Third
people
Second person
First person
person

Stopping
case
Can we simulate
this with code?
● Since we are doing
the same thing again
and again let’s use
one function to do
the task

7
Does this work?
def ask(person):

behind = ask(person + 1)
people = behind + 1

return people

8
 What happens?

behind = ask(person + 1)
people = behind + 1 behind = ask(person + 1)
people = behind + 1 behind = ask(person + 1)
people = behind + 1 behind = ask(person + 1)
return people
people = behind + 1
return people • • •
return people
return people

We will never get to return because we are calling

the function non stop. What should we do?

9
Does this work?
def ask(person):
if noMorePerson:
return 1

behind = ask(person + 1)
people = behind + 1

return people

10
What happens?

if noMorePerson:
return 1 if noMorePerson:
return 1 if noMorePerson:
return 1 if noMorePerson:
behind = ask(person + 1)
return 1
people = behind + 1 behind = ask(person + 1)
people = behind + 1 behind = ask(person + 1)
people = behind + 1 behind = ask(person + 1)
return people
people = behind + 1
return people
return people
return people

Then now we return the number of people to our

first caller

11
Definitions
Recursion: process in which a function calls itself directly
 Basic Concept

The basic concept of recursion is that a problem can be solved much

easily and in lesser time if it is represented in one or more smaller
versions.

What was the problem in the previous real life example?

What was the subproblem?

14
 Fundamental rules of recursion

● Base case is a terminating condition and it doesn’t use any recursive

calls to get answers

● Recurrence relation that reduces all cases towards base case

● State is an identifier that fully locate which subproblem we are dealing

with currently

15
 Recurrence Relation

How many
How many people behind
people you including
behind you yourself? Only Me
Let me
including
check…
yourself?
2 + 1= 3

How many
people are
there? There
are Two
State:
people
First State: Third
Caller: State: Second person
reception First person
person
Base Case
 state

def ask(person):
if noMorePerson:
return 1 Base Case

behind = ask(person + 1)
people = behind + 1 Recurrence
Relation
return people

17
 State

● Identifies the current subproblem completely

● Helps locate which subproblem we are dealing with currently
● Changes in state should lead towards base cases

18
 Base case

● are known and simplest cases of the problem

● is a terminating scenario
● initiate the process of returning to the original call function (or
problem)

19
 Recurrence Relation

● should be a breakdown of the current problem into smaller problems

● Is a set of cases reduces the current case towards base case
● It aggregates the result from recursive calls and returns the answer
we have so far to caller

20
Sample Question
 Solution

Q1. What happens if we continue to divide a number which is a power of four

by four?
● The final result will be 1

Q2. What if the number is not power of four?

● Their number will be below 1 eventually

From the above questions we can see that we have two base cases and the
state is the number that is divided by four every time we have recursive call.
 Dividing a power of four by four

64 / 16 / 4 / 1

Dividing a random number by four

28 / 7 / 1.75 / 0.44

24
Pair Programming
Power of four

25
Steps to solve a recursive problem
1. Break down the problem into smaller subproblems
2. Call the function to solve the smaller subproblems
3. Combine the result from the smaller subproblems to get the answer for the
bigger sub-problem

26
Let’s solve this problem using the three steps

27
1. Break down the problem into smaller problems

Power of three is a number made up of multiple 3 products

❏ 3•3•3•…•3

check first whether the number is divisible by 3

and then check whether the remaining factor is divisible by 3 recursively

❏ 3 • (3 • 3 • … • 3)
❏ 3 • 3 • (3 • … • 3)
❏ 3 • 3 • 3 • ( ...• 3)

If all checks are divisible by three, then the number must be power of three

28
 Is 27 divisible by three and
reduce Combine:
True
Is 9 = (27/3) divisible by three and
Combine:
reduce
True
Is 3 = (9/3) divisible by three and
reduce Combine:
Is 1 = (3/3) True

If 1 return True
Base Case
If 0 return False

29
2. Call the function to solve the smaller problems

Given that the current number is divisible by three

Check whether the rest of the number is divisible by three after dividing by
three

n % 3 == 0 and isPowerOfThree(n//3)

30
3. Combine the result from the smaller problems

The subproblems return whether the number was divisible by three

According to the subproblems, we can decide whether the number is power of

three or not

If the number is divisible by three and the number divided by three is recursively
divisible by three, the number is power of three

31
 Pair Programming
(swap between driver and passenger)
Power of three

32
Steps to follow to write recursive function

33
There are three things that needs to be
figured out for every recursive function

What are the three things?

34
The base case, State &
Recurrence relation

35
Base Case State Recurrence
Relation
● An answer that can ● A value that represent ● A relation between the
be computed without which subproblem we result of current
using recursive calls are currently tackling problem and its
subproblems
● It is the smallest and ● The subproblems
simplest case that is should reduce the
known current problem
eventually leading to
base case

36
Take out a notebook and write the base case and recurrence
relation for the problem below

37
Base Case
● If n == 1, return 1
● If n == 0, return 0

State
● n

Recurrence Relation
● f(n)=f(n-1)+f(n-2)

38
 Pair Programming
(swap between driver and passenger)
Fibonacci Number

39
How does recursion work?
Using Call Stack
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1)
two = fib(n-2)

return one + two

N=4
one = fib(3)
two = fib(2)

42
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1)
two = fib(n-2)

return one + two

N=3
one = fib(2)
two = fib(1)

N=4
one = fib(3)
two = fib(2)

43
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1) N=2

two = fib(n-2) one = fib(1)
two = fib(0)
return one + two

N=3
one = fib(2)
two = fib(1)

N=4
one = fib(3)
two = fib(2)

44
def fib(n: int) -> int:
if n == 1:
return 1
N=1
return 1
if n == 0:
return 0

one = fib(n-1) N=2

two = fib(n-2) one = fib(1)
two = fib(0)
return one + two

N=3
one = fib(2)
two = fib(1)

N=4
one = fib(3)
two = fib(2)

45
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1) N=2

two = fib(n-2) one = 1
two = fib(0)
return one + two

N=3
one = fib(2)
two = fib(1)

N=4
one = fib(3)
two = fib(2)

46
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1) N=2

two = fib(n-2) one = 1
two = fib(0)
return one + two

N=3
one = fib(2)
two = fib(1)

N=4
one = fib(3)
two = fib(2)

47
def fib(n: int) -> int:
if n == 1:
return 1
N=0
return 0
if n == 0:
return 0

one = fib(n-1) N=2

two = fib(n-2) one = 1
two = fib(0)
return one + two

N=3
one = fib(2)
two = fib(1)

N=4
one = fib(3)
two = fib(2)

48
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1) N=2

two = fib(n-2) one = 1
two = 0
return one + two

N=3
one = fib(2)
two = fib(1)

N=4
one = fib(3)
two = fib(2)

49
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0
N=2
one = fib(n-1) one = 1
two = fib(n-2) two = 0
return one + two
return one + two

N=3
one = fib(2)
two = fib(1)

N=4
one = fib(3)
two = fib(2)

50
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1)
two = fib(n-2)

return one + two

N=3
one = 1
two = fib(1)

N=4
one = fib(3)
two = fib(2)

51
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1)
two = fib(n-2)

return one + two

N=3
one = 1
two = fib(1)

N=4
one = fib(3)
two = fib(2)

52
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1) N=1

two = fib(n-2) return 1

return one + two

N=3
one = 1
two = fib(1)

N=4
one = fib(3)
two = fib(2)

53
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1)
two = fib(n-2)

return one + two

N=3
one = 1
two = 1
return one + two

N=4
one = fib(3)
two = fib(2)

54
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1)
two = fib(n-2)

return one + two

N=3
one = 1
two = 1
return one + two

N=4
one = fib(3)
two = fib(2)

55
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1)
two = fib(n-2)

return one + two

N=4
one = 2
two = fib(2)

56
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1)
two = fib(n-2)

return one + two

N=4
one = 2
two = fib(2)

57
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1)
two = fib(n-2)

return one + two

N=2
one = fib(0)
two = fib(1)

N=4
one = 2
two = fib(2)

58
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1) N=0

two = fib(n-2) return 0

return one + two

N=2
one = fib(0)
two = fib(1)

N=4
one = 2
two = fib(2)

59
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1)
two = fib(n-2)

return one + two

N=2
one = 0
two = fib(1)

N=4
one = 2
two = fib(2)

60
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1)
two = fib(n-2)

return one + two

N=2
one = 0
two = fib(1)

N=4
one = 2
two = fib(2)

61
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1) N=1

two = fib(n-2) return 1

return one + two

N=2
one = 0
two = fib(1)

N=4
one = 2
two = fib(2)

62
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1)
two = fib(n-2)

return one + two

N=2
one = 0
two = 1

N=4
one = 2
two = fib(2)

63
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1)
two = fib(n-2)

return one + two

N=2
one = 0
two = 1
return one + two

N=4
one = 2
two = fib(2)

64
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1)
two = fib(n-2)

return one + two

N=4
one = 2
two = 1

65
def fib(n: int) -> int:
if n == 1:
return 1

if n == 0:
return 0

one = fib(n-1)
two = fib(n-2)

return one + two

N=4
one = 2
two = 1
return 3

66
How does the recursion work?

● The system uses some ordering to execute the calls

● The ordering is done based on Last In First Out (depth first) order
○ It uses stack

[Link] -> currently executing

[Link] -> calling function
[Link] -> returning a value

67
Using Execution Tree
Step by Step Simulation
Go to this LINK
Depth of the
execution tree
Num of nodes
approximately
: 2n - 1

70
Reflection
● Why is the num of nodes for a full tree 2n - 1 ?
● Why is the depth of the execution tree n?
● In what order were we traversing the tree?

71
Complexity Analysis
 Time Complexity
(Any suggestion?)
 There are two parts
● Number of recursive calls
● The complexity of the function

74
How do we find the number of calls?
● Draw the execution tree
● Execution tree is a tree that describes the
flow of execution for the recursive function
● A node represents a call
● The total number of nodes is your final
answer

75
 Fib(4)

Facts: 20 4
● Two branching on each
node
21 3 2
● Height of the tree is the
equal to n
22 2 1 1 0
● In a full binary tree with n
height, we have 2n - 1 nodes
23 1 0

20 + 21 + … + 2n = 2n - 1
76
In general
● How many branching?
● What is the depth?

(Num of branching) depth of the tree

77
What is the complexity of the function?
● This is plain time and space complexity
analysis of the inner working of the function
● Are we doing any costly operations in the
function?

78
In Summary

O(function) • O((Num of branching) depth of the tree )

Cost of running function Number of recursive calls

79
Space Complexity
Before we discuss the space complexity, let’s consider these questions
● How does the computer run recursion function?
● How does it know when to return and combine?

80
It uses call stack

81
What is the space complexity of the call
stack?

82
Maximum size of the stack which is maximum
depth of the execution tree

83
Did we forget anything?

84
What about the states and space complexity
of the function?

85
In Summary
N=0
return 0

State Size + function N=2

complexity one = 1
two = fib(0)
depth
[O(states’ size) + O(space complexity of function) ] •
O(maximum depth of the execution tree ) N=3
one = fib(2)
two = fib(1)

N=4
one = fib(3)
two = fib(2)

86
 Reflection
● Can you draw execution tree for the previous problems you solved?
● In the simulation, what was the call stack?
● What is the max size of the call stack?
○ Depth of the execution tree
● In what order is the execution tree traversed?
○ Left Node first
○ Right Node second
○ Parent Node last
Checklist (Ask your instructor, if anything is missing)
❏ You have to be very comfortable with writing out the base case and
recurrence relation of recursive function
❏ You have to be very comfortable with drawing execution tree of a recursion
function
❏ Understanding the execution order using the execution tree
❏ Comfortably analyze the time and space complexity of a recursive function

88
Recursion versus Iteration

Anything that can be done recursively can be done iteratively

● Iteration is faster and more space-efficient than recursion.
● Recursion has function call overhead
● Iterative programs are easy to debug

So why do we even need recursion?

● It's easier to code a recursive approach for a given problem.
● Recursive codes are smaller and easier to understand.

89
Debugging
Debugging using the call stack
N=0
return 0
● Simulate the code using the
call stack
● Let’s go revisit the simulation N=2
one = 1
from the example on slide 48 two = fib(0)

N=3
one = fib(2)
two = fib(1)

N=4
one = fib(3)
two = fib(2)

91
Debugging using the execution tree
● Simulate the code using the
execution tree
● Let’s go revisit the simulation
from the example on slide 76

92
Debugging using print statements

● First notice that similar problems have similar solutions

○ recursive_function(n) == recursive_function(m) is always equal
given that n == m
4

3 2

2 1 1 0

1 0
93
Debugging using print statements:
def recursive_fn(state):
print(“state: “, state)

.
.
.

print(“result: “, result)
return result

94
 Recognizing in Questions
● Look for patterns in the question that suggest that the same
operation is being applied to smaller versions of the same
problem.
● Look for base cases or stopping conditions that define when
the recursion should end.
● Searching problems with branching conditions
Things to pay attention
Stack Overflow ?
Occurs when the program uses up the memory assigned to it in the call stack

In the case of recursion we will mainly deal with two types:

- Memory Limit Exceeded
- Maximum Recursion Depth Exceeded.

97
Memory Limit Exceeded

is a type of stack overflow error that occurs

when the parameters of our function take too
much space.

98
Maximum Recursion Depth Exceeded

is a type of stack overflow error that occurs when

the number of recursive calls being stored in the
call stack is greater than allowed.

Different programming languages have different

maximum recursion Depth sizes:
- Python => 1000
- Javascript => 10,000
- Java => around 10,000
- C++ =>No Limit

99
A function with missing base case

def fib(n: int) -> int:

if n == 1:
return 1

What happens when n == 0?

return fib(n-1) +
fib(n-2)

100
 Wrong recurrence relation

def numOfPeopleInQueue(n: int) -> int:

if n == 1:
return 1

prev = numOfPeopleInQueue(n-1) + 1
return prev + 1

We are doing + 1 unnecessarily

101
 Using list as state

def divideInBuckets(i, picked: List) -> int:

if i >= len(arr):
return 0

notPick = divideInBuckets(i+1,picked)
[Link](arr[i])
pick = divideInBuckets(i+1,picked) Passed by
reference

return pick + notPick

102
Practice Questions
Reverse String
Count Good Numbers
Pascal’s Triangle II
Merge Two Sorted List
Decode String
Predict the Winner
Power of three
Power of four
Resources
● Leetcode Recursion I Card
● Leetcode Recursion II Card
 Quote
“In order to understand recursion, one must first
understand recursion.”

Unknown