Recursion examples for Beginners (step by step code execution walkthrough with python code)
Factorial
Explanation and Example
Factorial Definition:
- The factorial of a non-negative integer n is the product of all positive integers less than or equal to n.
- It can be defined recursively as:
- factorial(0) = 1 (Base Case)
- factorial(n) = n * factorial(n-1) (Recursive Case)
+----------------------------------+
| factorial(n) |
| +---------------------------+
| | Base Case: |
| | factorial(0) = 1 |
| +---------------------------+
| | Recursive Case: |
| | factorial(n) = n * |
| | factorial(n-1)|
| +---------------------------+
+----------------------------------+
Python Code for Factorial
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
# Example Usage
print(factorial(5)) # Output: 120
Step-by-Step Execution Walkthrough
Initial Call: factorial(5)
Function Call Stack
factorial(5)
- Input: n = 5
- Calls: factorial(4)
Next Call
factorial(5)
factorial(4)
- Input: n = 4
- Calls: factorial(3)
Next Call
factorial(5)
factorial(4)
factorial(3)
- Input: n = 3
- Calls: factorial(2)
Next Call
factorial(5)
factorial(4)
factorial(3)
factorial(2) - Input: n = 2
- Calls: factorial(1)
Next Call
factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
- Input: n = 1
- Calls: factorial(0)
Base Case Reached
factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
factorial(0)
- Input: n = 0
- Returns: 1
Returning Values
factorial(1) returns 1 * 1 = 1
factorial(2) returns 2 * 1 = 2
factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24
factorial(5) returns 5 * 24 = 120 Tree-like Structure for factorial(5)
factorial(5) | |-- Select 5: | |-- factorial(4) | | | |-- Select 4: | | | |-- factorial(3) | | | |-- Select 3: | | | |-- factorial(2) | | | |-- Select 2: | | | |-- factorial(1) | | | |-- Select 1: | | | |-- factorial(0) | | | |-- Select 0: | | | |-- Returns 1 (Base Case) | |-- Returns 1 |-- Returns 1 * 1 = 1 |-- Returns 2 * 1 = 2 |-- Returns 3 * 2 = 6 |-- Returns 4 * 6 = 24 |-- Returns 5 * 24 = 120
Fibonacci Numbers
Explanation and Example
Fibonacci Definition:
- The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1.
- It can be defined recursively as:
- fibonacci(0) = 0 (Base Case)
- fibonacci(1) = 1 (Base Case)
- fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) (Recursive Case)
+-------------------------------------+
| fibonacci(n) |
| +------------------------------+
| | Base Case: |
| | fibonacci(0) = 0 |
| | fibonacci(1) = 1 |
| +------------------------------+
| | Recursive Case: |
| | fibonacci(n) = fibonacci( |
| | n-1) + fibonacci(n-2)|
| +------------------------------+
+-------------------------------------+
Python Code for Fibonacci
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
# Example Usage
print(fibonacci(5)) # Output: 5
Step-by-Step Execution Walkthrough
Initial Call: fibonacci(5)
Function Call Stack
fibonacci(5)
- Input: n = 5
- Calls: fibonacci(4) and fibonacci(3)
Next Call
fibonacci(5)
fibonacci(4)
- Input: n = 4
- Calls: fibonacci(3) and fibonacci(2)
Next Call
fibonacci(5)
fibonacci(4)
fibonacci(3)
- Input: n = 3
- Calls: fibonacci(2) and fibonacci(1)
Next Call
fibonacci(5)
fibonacci(4)
fibonacci(3)
fibonacci(2)
- Input: n = 2
- Calls: fibonacci(1) and fibonacci(0)
Base Cases Reached
- fibonacci(1): Returns 1
- fibonacci(0): Returns 0
Returning Values
fibonacci(2) returns 1 + 0 = 1
fibonacci(3) returns 1 + fibonacci(1) = 1 + 1 = 2
fibonacci(4) returns 2 + fibonacci(2) = 2 + 1 = 3
fibonacci(5) returns 3 + fibonacci(3) = 3 + 2 = 5Tree-like Structure for fibonacci(5)
fibonacci(5)
|
|-- Select 5:
|
|-- fibonacci(4)
| |
| |-- Select 4:
| |
| |-- fibonacci(3)
| |
| |-- Select 3:
| |
| |-- fibonacci(2)
| |
| |-- Select 2:
| |
| |-- fibonacci(1)
| |
| |-- Select 1:
| |
| |-- Returns 1 (Base Case)
| |
| |-- fibonacci(0)
| |
| |-- Select 0:
| |
| |-- Returns 0 (Base Case)
|
|-- Returns 1 + 0 = 1
|-- fibonacci(1)
| |
| |-- Select 1:
| |
| |-- Returns 1 (Base Case)
|
|-- Returns 1 + 1 = 2
|-- fibonacci(2)
| |
| |-- Select 2:
| |
| |-- fibonacci(1)
| |
| |-- Select 1:
| |
| |-- Returns 1 (Base Case)
| |
| |-- fibonacci(0)
| |
| |-- Select 0:
| |
| |-- Returns 0 (Base Case)
|
|-- Returns 1 + 0 = 1
|-- Returns 2 + 1 = 3
|-- fibonacci(3)
| |
| |-- Select 3:
| |
| |-- fibonacci(2)
| |
| |-- Select 2:
| |
| |-- fibonacci(1)
| |
| |-- Select 1:
| |
| |-- Returns 1 (Base Case)
| |
| |-- fibonacci(0)
| |
| |-- Select 0:
| |
| |-- Returns 0 (Base Case)
|
|-- Returns 1 + 0 = 1
|-- fibonacci(1)
| |
| |-- Select 1:
| |
| |-- Returns 1 (Base Case)
|
|-- Returns 1 + 1 = 2
|-- Returns 3 + 2 = 5
Permutations
Explanation and Example
Permutations Definition:
- A permutation is a re-arrangement of elements in a particular order.
- For a given set of n elements, there are n! (n factorial) possible permutations.
- It can be defined recursively as:
- Permutations of an empty list ([]) is an empty list.
- For each element in the list, we generate permutations by recursively permuting the rest of the elements and combining them.
+-----------------------------------------+
| permutations(lst) |
| +----------------------------------+
| | Base Case: |
| | permutations([]) = [[]] |
| +----------------------------------+
| | Recursive Case: |
| | For each element in lst: |
| | Recursively permute rest |
| | Combine with current element|
| +----------------------------------+
+-----------------------------------------+
Python Code for Permutations
def permutations(lst):
if len(lst) == 0:
return [[]]
perm_list = []
for i in range(len(lst)):
elem = lst[i]
rest = lst[:i] + lst[i+1:]
for p in permutations(rest):
perm_list.append([elem] + p)
return perm_list
# Example Usage
print(permutations([1, 2, 3]))
Step-by-Step Execution Walkthrough
Initial Call: permutations([1, 2, 3])
Function Call Stack
permutations([1, 2, 3])
- Input: lst = [1, 2, 3]
- Calls: permutations([2, 3]), permutations([1, 3]), permutations([1, 2])
Case 1: permutations([2, 3])
permutations([1, 2, 3])
permutations([2, 3])
- Input: lst = [2, 3]
- Calls: permutations([3]), permutations([2])
Next Call: permutations([3])
permutations([1, 2, 3])
permutations([2, 3])
permutations([3])
- Input: lst = [3]
- Calls: permutations([])
Base Case Reached
- permutations([]): Returns [[]]
Returning Values
permutations([3]) returns [[3]]
permutations([2, 3]) returns [[2, 3], [3, 2]]
Case 2: permutations([1, 3])
permutations([1, 2, 3])
permutations([1, 3])
- Input: lst = [1, 3]
- Calls: permutations([3]), permutations([1])
Next Call: permutations([3])
permutations([1, 2, 3])
permutations([1, 3])
permutations([3])
- Input: lst = [3]
- Calls: permutations([])
Base Case Reached
- permutations([]): Returns [[]]
Returning Values
permutations([3]) returns [[3]]
permutations([1, 3]) returns [[1, 3], [3, 1]]
Case 3: permutations([1, 2])
permutations([1, 2, 3])
permutations([1, 2])
- Input: lst = [1, 2]
- Calls: permutations([2]), permutations([1])
Next Call: permutations([2])
permutations([1, 2, 3])
permutations([1, 2])
permutations([2])
- Input: lst = [2]
- Calls: permutations([])
Base Case Reached
- permutations([]): Returns [[]]
Returning Values
permutations([2]) returns [[2]]
permutations([1, 2]) returns [[1, 2], [2, 1]]
Final Returning Values
permutations([1, 2, 3]) returns [
[1, 2, 3], [1, 3, 2], [2, 1, 3],
[2, 3, 1], [3, 1, 2], [3, 2, 1]
]
Tree-like Structure for permutations([1, 2, 3])
permutations([1, 2, 3])
|
|-- Select 1:
|
|-- permutations([2, 3])
| |
| |-- Select 2:
| |
| |-- permutations([3])
| | |
| | |-- Select 3:
| | |
| | |-- permutations([])
| | | |
| | | |-- [[]]
| | |
| | |-- returns [[3]]
| |
| |-- Select 3:
| |
| |-- permutations([])
| | |
| | |-- [[]]
| |
| |-- returns [[2]]
|
|-- returns [[2, 3], [3, 2]]
|
|-- Select 2:
|
|-- permutations([1, 3])
| |
| |-- Select 1:
| |
| |-- permutations([3])
| | |
| | |-- Select 3:
| | |
| | |-- permutations([])
| | | |
| | | |-- [[]]
| | |
| | |-- returns [[3]]
| |
| |-- Select 3:
| |
| |-- permutations([1])
| | |
| | |-- permutations([])
| | | |
| | | |-- [[]]
| | |
| | |-- returns [[1]]
|
|-- returns [[1, 3], [3, 1]]
|
|-- Select 3:
|
|-- permutations([1, 2])
| |
| |-- Select 1:
| |
| |-- permutations([2])
| | |
| | |-- Select 2:
| | |
| | |-- permutations([])
| | | |
| | | |-- [[]]
| | |
| | |-- returns [[2]]
| |
| |-- Select 2:
| |
| |-- permutations([1])
| | |
| | |-- permutations([])
| | | |
| | | |-- [[]]
| |
| |-- returns [[1]]
|
|-- returns [[1, 2], [2, 1]]
|
|-- Final Result: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Support Our Efforts and Earn Together 🚀
Visit https://parucodes.github.io/ today and start your journey to becoming a fast, accurate, and confident touch typist.
If you find our website useful and want to support us, consider joining the exciting world of Bitcoin mining on your mobile phone. Follow this link: Mine PI Bitcoin and use my username prarthanadp as your invitation code. With the referral code prarthanadp, you'll receive a special referral bonus.
Thank you for your support! Let's grow and earn together! 🌟
Comments
Post a Comment