Recursive

Algorithms

Recursion
Recursive Method

Examples
Computer Science Faculty - Software Factorial
Fibonacci Sequence

Engineering
Analysis of Algorithms

Analysis of Algorithms‘ Course Lectures

( Recursive Algorithms )

Ali Shah Saber

alishah.saber@gmail.com | telegram: @alishahsaber
Fall, 2024
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Recursive
Session Overview Algorithms

Recursion
Recursive Method

Examples
Factorial
Fibonacci Sequence

1 Recursion
Recursive Method

2 Examples
Factorial
Fibonacci Sequence

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Recursive
Recursion Algorithms

Recursion
Iteration Recursive Method

• for statement Examples

Factorial

• while statement Fibonacci Sequence

Technique in which a method call itself. Easy way for

complex problems
• Each time the parameter become smaller.

Drawbacks
• Non-efficiency for some problems
• Overhead
• Base case definition
• Parameters
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Recursive
Recursion Algorithms

Recursion
Recursive Method

For recursion to be correct, there should be a “Yes” Examples

answer for the following 3 questions: Factorial
Fibonacci Sequence

1 Is there another solutions for the problem?

2 Is the smaller form of the problem is the same as the
whole problem?
3 Is the whole method is working correctly?

To solve a problem recursively do the following:

1 Specify the problem
2 Specify the size of the problem for each call
3 Specify the base case (s)
4 Specify the general case (s)
. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Recursive
Factorial Algorithms

Recursion
Recursive Method

Examples
Factorial
Fibonacci Sequence

• n! = n ∗ (n − 1) ∗ (n − 2) ∗ ....3 ∗ 2 ∗ 1
{
1 if n = 0
N! =
n(n − 1)! if n > 0

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Recursive
Factorial Algorithms

Recursion
Recursive Method

Examples
Factorial
Fibonacci Sequence

(1) Write and Implement a Recursive Algorithm Function

for Factorial Calculation?
(2) Trace and Simulate with Specific Instances!

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Recursive
Fibonacci Sequence Algorithms

Recursion
Recursive Method

Examples
Factorial
Fibonacci Sequence

Fibonacci numbers of Fibonacci Sequence Numbers

• F0 = 0,
• F1 = 1,
• Fi = Fi−1 + Fi−2 , for i ≥ 2

e.g.
• 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
Fibonacci Sequence

Recursive Procedure Instances of Fibonacci Numbers

. . . .... .... .... . . . . .

 Recursive
Fibonacci Sequence Algorithms

Recursion
Recursive Method

Examples
Factorial
Fibonacci Sequence

(1) Write and Implement a Recursive Algorithm/Function

for Fibonacci Sequence Calculation?

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 Recursive
Exercise Algorithms

Recursion
Recursive Method

Write a recursive method to calculate power of Examples

Factorial

numbers Fibonacci Sequence

• e.g. XY

Write a recursive method for Euclidean Algorithm

(GCD)
• e.g. GCD(60, 25)

Write a recursive method for Binomial Coefficients

(Pascal)
• e.g. (x + 1)6 = x6 + 6x5 + 15x4 + 20x3 + 15x2 + 6x + 1

. . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . .
 The End
Questions? Comments?

. . . .... .... .... . . . . .