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?
. . . .... .... .... . . . . .
