Scribd
Upload
6 views19 pages

04 Recursion

The document discusses recursion as a problem-solving technique where a function calls itself, providing examples such as factorial calculation, the Tower of Hanoi, and palindrome checking. It also covers the analysis of recursive algorithms, including their time complexity and growth rates, with specific examples demonstrating how to derive these complexities. Additionally, it highlights the importance of worst-case analysis in understanding algorithm performance.

Uploaded by

busraaktasaal2002
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views19 pages

04 Recursion

The document discusses recursion as a problem-solving technique where a function calls itself, providing examples such as factorial calculation, the Tower of Hanoi, and palindrome checking. It also covers the analysis of recursive algorithms, including their time complexity and growth rates, with specific examples demonstrating how to derive these complexities. Additionally, it highlights the importance of worst-case analysis in understanding algorithm performance.

Uploaded by

busraaktasaal2002
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

10/30/2024

CENG 310
Data Structures and Algorithms
with Python

Recursion

CENG310 Data Structures and Algorithms with Python

Content

Definition & Examples


Analysis Approaches
Linear, Binary & Multiple Recursion

CENG310 Data Structures and Algorithms with Python

1
10/30/2024

What is recursion?

A problem solving technique by which a function makes calls to


itself.
Many examples in art and nature (e.g., fractals).
A powerful alternative for iterative tasks.

CENG310 Data Structures and Algorithms with Python

Recursion
What Examples
is recursion?
base condition
induction

def fact(n):
if n == 0:
return 1
else:
return n * fact(n - 1)

CENG310 Data Structures and Algorithms with Python

2
10/30/2024

Recursion Callstack Example

call: fact(0)
if n==0:
> return 1
C else:
A return (0*fact(-1))
call: fact(1) call: fact(1) call: fact(1)
L if n==0: if n==0: if n==0:
L return 1 return 1 return 1
else: else: else:
> return (1*fact(0)) > return (1*fact(0)) > return (1*1)
S call: fact(2) call: fact(2) call: fact(2) call: fact(2) call: fact(2)
if n==0: if n==0: if n==0: if n==0: if n==0:
T return 1 return 1 return 1 return 1 return 1
A else: else: else: else: else:
> return (2*fact(1)) > return (2*fact(1)) > return (2*fact(1)) > return (2*fact(1)) > return (2*1)
C call: fact(3) call: fact(3) call: fact(3) call: fact(3) call: fact(3) call: fact(3) call: fact(3)
K if n==0: if n==0: if n==0: if n==0: if n==0: if n==0: if n==0:
return 1 return 1 return 1 return 1 return 1 return 1 return 1
else: else: else: else: else: else: else:
> return (3*fact(2)) > return (3*fact(2)) > return (3*fact(2)) > return (3*fact(2)) > return (3*fact(2)) > return (3*fact(2)) > return (3*2)
Third recursive call's Second recursive First recursive call's
First call First recursive call Second recursive call Third recursive call
execution is over. call's execution is execution is over.

CENG310 Data Structures and Algorithms with Python

Recursion Callstack Example


call: fact(0)
if n==0:
> return 1
C else:
return (0*fact(-1))
A
call: fact(1) call: fact(1)
L if n==0: if n==0:
L else:
return 1
else:
return 1

> return (1*fact(0)) > return (1*fact(0))


S call: fact(2) call: fact(2) call: fact(2)
if n==0: if n==0: if n==0:
T return 1 return 1 return 1
A else: else: else:
> return (2*fact(1)) > return (2*fact(1)) > return (2*fact(1))
C call: fact(3) call: fact(3) call: fact(3) call: fact(3)
K if n==0: if n==0: if n==0: if n==0:
return 1 return 1 return 1 return 1
else: else: else: else:
> return (3*fact(2)) > return (3*fact(2)) > return (3*fact(2)) > return (3*fact(2))

First call First recursive call Second recursive call Third recursive call

CENG310 Data Structures and Algorithms with Python

3
10/30/2024

Recursion Callstack Example

C
A
call: fact(1)
if n==0: L
else:
return 1
L
> return (1*1)
call: fact(2) call: fact(2) S
if n==0: if n==0:
return 1 return 1 T
else: else: A
> return (2*fact(1)) > return (2*1)
call: fact(3) call: fact(3) call: fact(3) C
if n==0: if n==0: if n==0: K
return 1 return 1 return 1
else: else: else:
> return (3*fact(2)) > return (3*fact(2)) > return (3*2)
Third recursive call's Second recursive First recursive call's
execution is over. call's execution is execution is over.

CENG310 Data Structures and Algorithms with Python

Recursion Examples

def fact(n):
if n == 0: c1
return 1 c2 T(n)
else:
return n * fact(n - 1)
c3 T(n-1)

T(0) = c1 + c2 = c
T(n) = T(n-1) + c3 = T(n-1) + c
= (T(n-2) + c) + c
= (T(n-3) + c) + c + c
= (T(n-i) + i*c)
when i=n  T(0) + n*c  T(n) = O(n)

CENG310 Data Structures and Algorithms with Python

4
10/30/2024

Recursion Examples
The Tower of Hanoi

Goal: Move all disks on pole 1 to pole 3


Rules:
• One move at a time
• One Move: Take the topmost disk from
any pole and place it on top of another
stack at another pole
• At any time, no larger disk may be placed
on top of a smaller disk

CENG310 Data Structures and Algorithms with Python

Recursion Examples
The Tower of Hanoi

def hanoi(n, source, dest, spare): # Cost


if (n > 0): # c1
hanoi(n-1, source, spare, dest) # T(n-1)
print(f' Move top disk from pole {source} to pole {dest}’) #c2
hanoi(n-1, spare, dest, source) # T(n-1)

CENG310 Data Structures and Algorithms with Python

5
10/30/2024

Recursion Examples
The Tower of Hanoi (call tree)
'A' 'B' 'C'
hanoi(3,'A','B','C')
print('A --> B')
hanoi(2,'A','C','B') 4 hanoi(2,'C','B','A')
2 6
print('A --> C') print('C --> B')

hanoi(1,'A','B','C') hanoi(1,'B','C','A') hanoi(1,'C','A','B') hanoi(1,'A','B','C')

1 3 5 7
print('A --> B') print('B --> C') print('C --> A') print('A --> B')
hanoi(0,…) hanoi(0,…)
hanoi(0,…) hanoi(0,…) hanoi(0,…) hanoi(0,…) hanoi(0,…) hanoi(0,…)

def hanoi(n, source, dest, spare): # Cost


if (n > 0): # c1
hanoi(n-1, source, spare, dest) # T(n-1)
print(f' Move top disk from pole {source} to pole {dest}’) #c2
hanoi(n-1, spare, dest, source) # T(n-1)

CENG310 Data Structures and Algorithms with Python

Recursion Examples
The Tower of Hanoi (call tree)
'A' 'B' 'C'

CENG310 Data Structures and Algorithms with Python

6
10/30/2024

Recursion Examples
The Tower of Hanoi
What is the cost of hanoi(n,'A','B','C')?

when n=0
T(0) = c1
when n>0
T(n) = c1 + T(n-1) + c2 + T(n-1)
= 2*T(n-1) + (c1+c2)
= 2*T(n-1) + c

Recurrence equation for the growth-rate function of the Tower of Hanoi


algorithm.

CENG310 Data Structures and Algorithms with Python

Recursion Examples
Methodology: repeated substitutions
T(n) = 2*T(n-1) + c
= 2 * (2*T(n-2)+c) + c
= 2 * (2* (2*T(n-3)+c) + c) + c
= 23 * T(n-3) + (22+21+20)*c (assuming n>2)
when substitution repeated (i-1)th times
= 2i * T(n-i) + (2i-1+ ... +21+20)*c
when i=n
= 2n * T(0) + (2n-1+ ... +21+20)*c
n− 1
= 2n * c1 + ( ∑ 2i)*c
i= 0

= 2n * c1 + ( 2n-1 )*c = 2n*(c1+c) – c  So, the growth rate function is O(2n)

CENG310 Data Structures and Algorithms with Python

7
10/30/2024

Recursion Examples
Palindrome
Sequence of symbols that reads the same backward as forward
e.g., Al lets Della call Ed “Stella.”, Borrow or rob?

def isPalindrome (s):


if (len(s) <= 1):
return True
return (s[0]==s[len(s)-1]) and isPalindrome(s[1:len(s)-1])

T(n) = T(n-2) + c
= (T(n-4) + c) + c
= (T(n-6) + c) + c + c
= (T(n-i) + i/2*c)
when i=n  T(0) + n/2*c  T(n) = O(n)
CENG310 Data Structures and Algorithms with Python

Recursion Examples
Fibonacci Numbers
Fibonacci numbers form a sequence (i.e., Fibonacci sequence)
such that each number is the sum of the two preceding ones.

CENG310 Data Structures and Algorithms with Python

8
10/30/2024

Recursion Examples

def fib(n): # 1 1 2 3 5 8 13 21 34 ..
if (n == 1):
return 1
if (n == 2):
return 1
else:
return fib(n-1) + fib(n-2)

T(n) = ?

CENG310 Data Structures and Algorithms with Python

Recursion Examples

def fib(n): # 1 1 2 3 5 8 13 21 34 ..
if (n == 1):
return 1
if (n == 2):
return 1
else:
return fib(n-1) + fib(n-2)

T(n) = T(n-1) + T(n-2) + c


= (T(n-2) + T(n-3) + c) + (T(n-3) + T(n-4) + c) + c
= gets nasty if we continue substituting; let’s find a better way.

CENG310 Data Structures and Algorithms with Python

9
10/30/2024

Recursion Examples

def fib(n): # 1 1 2 3 5 8 13 21 34 ..
if (n == 1) or (n == 2):
return 1
else:
return fib(n-1) + fib(n-2)

T(n) = T(n-1) + T(n-2) + c


T(n-1) + T(n-2) + c < T(n-1) + T(n-1) + c = O(2n) (recall the solution in Hanoi towers)
This shows that it cannot exceed O(2n), hence an upper bound.

CENG310 Data Structures and Algorithms with Python

Recursion Examples
If we can find a lower bound for T(n) and show that it is also (2n),
then we can say that T(n) is (2n).

T(n-1) + T(n-2) + c > T(n-2) + T(n-2) + c (because T(n-1) > T(n-2) slightly.)
T(n) = 2T(n-2) + c
= 2(2T(n-4) + c) + c = 4T(n-4) + 3c
= 2(2(2T(n-6) + c) + c) + c = 8T(n-6) + 7c
=… = 16T(n-8) + 15c
= 2iT(n-2i) + (2i-1)
when i = n/2  2n/2T(0) + 2n/2-1 = (2n) is the lower bound for T(n).

CENG310 Data Structures and Algorithms with Python

10
10/30/2024

Recursion Examples
Better Option: Fibonacci in O(n)

CENG310 Data Structures and Algorithms with Python

Recursion Examples
Better Option: Fibonacci in O(n)

T(n) = T(n-1) + c1
T(1) = c0

fib(4)=(3,2)
fib(3)=(2,1)

fib(2)=(1,1)
fib(1)=(1,0)

0, 1, 1, 2, 3, 5, 8, 13, 21, 34
CENG310 Data Structures and Algorithms with Python

11
10/30/2024

Analysis Approaches
An algorithm can require different times to solve different
problems of the same size.
Example:
• Searching an item in a list of n elements using sequential search.
• The cost could be anywhere between 1 and n value-check operations.

Worst-case Analysis – The maximum amount of time that an


algorithm require to solve a problem of size n.
• This gives an upper bound for the time complexity of an algorithm.
• Normally, we try to find worst-case behavior of an algorithm.

CENG310 Data Structures and Algorithms with Python

Analysis Approaches
Best-case Analysis – The minimum amount of time that an
algorithm require to solve a problem of size n.
• The best case behavior of an algorithm is NOT so useful.

Average-case Analysis – The average amount of time that an


algorithm require to solve a problem of size n.
• Sometimes, it is difficult to find the average-case behavior of an algorithm.
• We might need to investigate all possible data organizations of a given size n,
and their distribution probabilities of these organizations.

Worst-case analysis is more common than average-case analysis.

CENG310 Data Structures and Algorithms with Python 24

12
10/30/2024

Sequential Search
def sequential_search(item_list, item):
for i in range(len(item_list)):
if item == item_list[i]:
return item
return -1

Unsuccessful Search: n+1 searches would be performed. O(n)

Successful Search:
Best-Case: item is in the first location of the array O(1)
Worst-Case: item is in the last location of the array O(n)
Average-Case: The number of item checks n
would be 1, 2, ..., n  O(n) ∑i
i=1 ( n 2 +n)/2
=
n n

CENG310 Data Structures and Algorithms with Python 25

Binary Search
Binary search on a sorted array
def binary_search(arr, low, high, x):
if high >= low: # Check base case
mid = (high + low) // 2
if arr[mid] == x: # In middle? Return itself
return mid
# Smaller than mid? Has to be in left subarray
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else: # Else? Has to be in right subarray
return binary_search(arr, mid + 1, high, x)
else: # Element is not present in the array
return -1 Base condition
Borrowed from GeeksForGeeks: [Link]

CENG310 Data Structures and Algorithms with Python

13
10/30/2024

Binary Search
0 1 2 3 4 5 6 7 8 9
Find:
2 5 8 12 16 23 38 56 72 91
16
0 1 2 3 4 5 6 7 8 9
2 5 8 12 16 23 38 56 72 91
Check:
16 √
0 1 2 3 4 5 6 7 8 9
2 5 8 12 16 23 38 56 72 91

0 1 2 3 4 5 6 7 8 9
2 5 8 12 16 23 38 56 72 91

0 1 2 3 4 5 6 7 8 9
2 5 8 12 16 23 38 56 72 91

CENG310 Data Structures and Algorithms with Python

Binary Search
0 1 2 3 4 5 6 7 8 9
Find:
2 5 8 12 16 23 38 56 72 91
23
0 1 2 3 4 5 6 7 8 9
2 5 8 12 16 23 38 56 72 91
Check:
16
0 1 2 3 4 5 6 7 8 9 56
2 5 8 12 16 23 38 56 72 91 23 √

0 1 2 3 4 5 6 7 8 9
2 5 8 12 16 23 38 56 72 91

0 1 2 3 4 5 6 7 8 9
2 5 8 12 16 23 38 56 72 91

CENG310 Data Structures and Algorithms with Python

14
10/30/2024

Binary Search
0 1 2 3 4 5 6 7 8 9
Find:
2 5 8 12 16 23 38 56 72 91
92
0 1 2 3 4 5 6 7 8 9
2 5 8 12 16 23 38 56 72 91
Check:
16
0 1 2 3 4 5 6 7 8 9 56
2 5 8 12 16 23 38 56 72 91 72
91
0 1 2 3 4 5 6 7 8 9 X
2 5 8 12 16 23 38 56 72 91

0 1 2 3 4 5 6 7 8 9
2 5 8 12 16 23 38 56 72 91

CENG310 Data Structures and Algorithms with Python

Binary Search Analysis

CENG310 Data Structures and Algorithms with Python

15
10/30/2024

File Systems

Directory

File Directories

Files

CENG310 Data Structures and Algorithms with Python

File Systems

[Link](path)
[Link](path)
[Link](path)
[Link](path, filename)

CENG310 Data Structures and Algorithms with Python

16
10/30/2024

File Systems
disk_usage(‘/user/rt/course’)

disk_usage(‘/user/rt/course/cs016’) disk_usage(‘/user/rt/course/cs252’)

... ...
disk_usage(‘/user/rt/course/cs016/grades’)
...

CENG310 Data Structures and Algorithms with Python

Linear Recursion
The maximum number of recursive calls that may be started from
within the body of a single activation: 1

Fibonacci

Factorial
Recursion 1

CENG310 Data Structures and Algorithms with Python

17
10/30/2024

Binary Recursion
The maximum number of recursive calls that may be started from
within the body of a single activation: 2
def fib(n): # 1 1 2 3 5 8 13 21 34 ..

Fibonacci if (n == 1):
return 1
if (n == 2):
return 1
else: Recursion 1 Recursion 2
return fib(n-1) + fib(n-2)

CENG310 Data Structures and Algorithms with Python

Multiple Recursion
The maximum number of recursive calls that may be started from
within the body of a single activation: >2

Disk space usage of file system

Recursion 1..n

CENG310 Data Structures and Algorithms with Python

18
10/30/2024

Remarks

READING:
The material at the end of the Chapter 4

CENG310 Data Structures and Algorithms with Python

19

You might also like