CSC 4520/6520

Design & Analysis of Algorithms

CHAPTER 2: RECURSIVE ALGORITHMS
Abdullah Bal, PhD

1
 Objectives

Recap
Asymptotic Order of Growth
Analysis of What is Memoization
L’Hopital Loops recursion
Stirling and
Nonrecursive Algorithms
- Maximum element
recursive
-Element Uniqueness algorithm?
-Matrix Multiplications
-Counting Binary Digits

2
Analysis of Algorithms: For Loop
o Incrementing for loop

for (i=0, i<n, i++) n+1

{
Statements; n

Time complexity: Θ (n)

3
Analysis of Algorithms: For Loop
o Decrementing for loop

for (i=n, i>0, i--) n+1

{
Statements; n

Time complexity: Θ (n)

4
Analysis of Algorithms: For Loop
for (i = 1, i < n, i=i+2)
{
Statements; n/2

Time complexity: Θ (n)

5
Analysis of Algorithms: For Loop
m=0 i m
for (i = 1, m <=n, i ++) 1 0+1
{ 2 1+2
m=m+i; 3 1+2+3
} 4 1+2+3+4
o When i=k, m becomes greater than n (m>n) . .
o m=1+2+3+…..+k=k(k+1)/2 . .
o k(k+1)/2 >n
o k> 𝑛
k 1+2+3+4+…….+k

Time complexity: Θ ( 𝑛)
6
Analysis of Algorithms: For Loop
for (i=n, i>=1, i=i/2) i
{ n
Statements; n/2
n/22
}
n/23
.
"
i = #! = 1 .
n = 2k n/2k
Time complexity: Θ (log2n)
7
Analysis of Algorithms: For Loop
for (i=1, i<=n, i++) for (i=1, i<n, i=i*2)
{ {
Statements; Statements;

} }

i=1+1+1+1+………+1=n i=1*2*2*2*2*2*…*2=n
k=n 2k = n
Time complexity: Θ (n) Time complexity: Θ (log2n)

8
Analysis of Algorithms: For Loops
for (i = 0, i < n, i++)
{
Statements; n

}
for (i = 0, i < n, i++)
{
Statements; n

}
Total = 2n

Time complexity: Θ (n)

9
Analysis of Algorithms: Nested For Loops
for (i = 0, i < n, i ++) n+1
{
for (j = 0, j < n, j ++) n * (n+1)
{
Statements; n * n

}
} Time complexity: Θ (n2)

11
Analysis of Algorithms: For Loops
for (i = 0, i < n, i++) Θ (n)
for (i = 0, i < n, i=i+2) n/2 Θ (n)
for (i = n, i > n, i--) Θ (n)

for (i = 1, i < n, i=i*2) Θ (log 2 n)

for (i = 1, i < n, i=i*3) Θ (log 3 n)
for (i = n, i > 1, i=i/2) Θ (log 2 n)

14
Analysis of Algorithms: If & While
i=0 1 for (i = 0, i < n, i ++) n+1
while ( i < n) n+1 {
{ Statements;
Statements; n n
i++; n }

}
f(n)= 3n+2 f(n)= 2n+1

Time complexity: Θ (n) Time complexity: Θ (n)

15
Analysis of Algorithms: If & While
i = 1;
m = 1; i m
while (m <n) 1 1
{ 2 1+1=2
Statements; 3 2+2
m=m+i;
i++; 4 2+2+3
} 5 2+2+3+4
When i=k, m becomes equal to n (m=n) . .
m=n=1+2+3+…..+k=k(k+1)/2
k(k+1)/2 >n k 2+2+3+4+…….+k
k> 𝑛
Time complexity: Θ ( 𝑛)
17
Analysis of Algorithms: If & While
function unknown(n)
{
if (n<7)
{
printf(“%d”,n); 1
}
else
{
for (i = 0, i < n, i++)
{
printf(“%d”,i); n
}
}
} Time complexity: Θ (n)
19
RECURSION

20
What is recursion?
Recursion is a technique in programming where a function calls itself in order to
solve a problem.

def biggest():
biggest()

21
 Recursion in shapes

Sierpinski’s triangles
The recursive centaur (Mythical creature).
Image by Joseph Parker.

[Link] 22
 Recursive cartoon

Bart simpson-Homer simpson

[Link]
23
Definition of recursion nature
o If problems are solved by reducing them to smaller problems of
the same form, it is said to have recursion nature

o It can be a powerful tool for solving problems that have a

recursive structure

24
Factorial has a recursive nature?

n!= n x (n-1) x (n-2) x (n-3) x …..2 x 1

n!= n x (n-1)!

25
Factorial has a recursive nature

5! = 5 x 4 x 3 x 2 x 1 = 120
4! = 4 x 3 x 2 x 1 = 24
5! = 5 x 4! = 120

26
Recursive factorial function
n! = n x (n-1)!

def factorial(n):
return n * factorial(n-1)

print(factorial(5))

27
Recursive factorial function
RecursionError Traceback (most recent call last)
[Link] Cell 3' in <cell line: 4>()
….
[... skipping similar frames: factorial at line 2 (2970 times)]

[Link] Cell 3' in factorial(number)

1 def factorial(number):
----> 2 return number * factorial(number-1)

RecursionError: maximum recursion depth exceeded

28
Recursive factorial function

5! = 5 x 4 x 3 x 2 x 1 x 0 x -1 x -2 x…..

RecursionError: maximum recursion depth exceeded

• A stack oveflow is when a recursive function gets out of

control and does not stop recursing

29
Base Case - Recursive Case
Hint: 1!=1
def factorial(number):
if number == 1:
return 1 # Base Case
return number * factorial(number-1) # Recursive Case

print(factorial(5))

• Recursive function must always have at least

one Base Case and one Recursive Case.

30
Visualizing Recursion
fact (5)
def fact(num): num = 5
if num == 1: Because num != 1
return 1 return 5*fact(4);
fact (4)
return num * fact(num-1) num = 4
Because num != 1
return 4*fact(3);
fact (3)
num = 3

fact (5)= ? Because num != 3

return 3*fact(2);
fact (2)
num = 2
Because num != 1
return 2*fact(1);
fact (1)
num = 1
Because num == 1
return 1;

31
Recursion-Limitations

factorial(3000)

RecursionError: maximum recursion depth exceeded in comparison

• Python has a limit of 2970 function calls.

32
Iterative factorial function
def factorial(number):
fact=1
for i in range(1,number+1):
fact = fact * i
return fact

print(factorial(5))

33
Recursion or Iteration?
o In recursion, the function calls itself until it reaches the base case,
o In iteration, the program executes a loop until a condition is met.
o Memory Usage:
o Recursion can be memory-intensive, as each recursive call adds a new
entry to the call stack, which can potentially lead to a stack overflow
error.
o On the other hand, iteration typically uses less memory because it
doesn't add new entries to the call stack.

34
Recursion or Iteration?
o Code Complexity:
o Recursive solutions can be easier to read and understand for problems
that have a recursive structure,
o Iterative solutions may require more complex code.

o Performance:
o Recursive solutions can be slower than iterative solutions due to the
overhead of function calls and the potential for stack overflow errors.
o However, some problems may be better suited for recursion and may
have faster recursive solutions than iterative ones.

35
 Activity: Computing Power
oWrite a recursive function that takes in a number (x) and an exponent (n) and
returns the result of 𝑥 !

def power(x , n):

if n == 0:
return 1 # Base Case
return x * power(x,n-1) # Recursive Case

36
What is excessive repetition in recursion?
oWhen recursive algorithms are designed carelessly, it can lead to very inefficient
and unacceptable solutions.

o For example, let us consider the Fibonacci sequence

1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 . . . . .

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

fib(1) and fib(2) = 1

37
Recursive function for Fibonacci
def fib(number):
if number == 1 or number == 2:
return 1 # Base case
else:
return fib(number-2) + fib(number -1) # Recursive case

38
Excessive repetition in recursion
oRecursive Fibonacci ends up repeating the same computation numerous times.
oLet nk be the number of recursive calls by fib(k)
• n0 = 1
• n1 = 1
• n2 = n1 + n0 + 1 = 1 + 1 + 1 = 3
• n3 = n2 + n1 + 1 = 3 + 1 + 1 = 5
• n4 = n3 + n2 + 1 = 5 + 3 + 1 = 9
• n5 = n4 + n3 + 1 = 9 + 5 + 1 = 15
• n6 = n5 + n4 + 1 = 15 + 9 + 1 = 25
• n7 = n6 + n5 + 1 = 25 + 15 + 1 = 41
• n8 = n7 + n6 + 1 = 41 + 25 + 1 = 67

o Note that nk at least doubles every other time

39
Visualizing Recursive Fibonacci
fib(5)

fib(4) fib(3)

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

1 1 1

fib(2) fib(1)

1 1

40
Visualizing Recursive Fibonacci
fib(5)

fib(4) fib(3)

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

1 1 1

fib(2) fib(1)

1 1

41
Recursive Fibonacci with Memoization
Fib_Cache = {}

def fib(number):
if number in Fib_Cache:
return Fib_Cache[number]

if number == 1 or number == 2:
return 1 # Base case
else:
Fib_Cache[number] = fib(number-2) + fib(number -1) # Recursive case
return Fib_Cache[number]

42
Recursive analysis of factorial?

0! = 1
Recursive definition of n!: F(n) = F(n-1) × n for n ≥ 1

43
Summary
o Analysis of Loops (For-If-While)
o Recursion (Base Case, recursive case)
o Memoization

44
 Supportive Materials
o Introduction to The Design and Analysis of Algorithms (3rd Edition) by Anany
Levitin, Pearson.
o Introduction to Algorithms, by [Link], C. Leiserson, [Link] and [Link],
MIT Press, 3rd Edition.

45