Recursion for Beginners (with python code)
Understanding Recursion
Recursion is a programming technique where a function calls itself in order to solve a problem. Recursive functions typically have a base case and a recursive case.
1. What is Recursion?
Recursion is when a function calls itself to solve smaller instances of the same problem. Recursion can be used to break down complex problems into simpler, more manageable parts.
+-----------------------------+
| Start |
| +---------------------+
| | Recursive Function |
| +---------------------+
| | Calls Itself |
| +---------------------+
| | Base Case (Stops) |
| +---------------------+
| End |
+-----------------------------+
2. When and Where to Use Recursion
Use Recursion when:
- The problem can be divided into smaller, similar problems.
- You need a cleaner and more intuitive solution for problems like tree traversals, sorting, etc.
Avoid Recursion if:
- The problem can be solved more efficiently with loops.
- Stack overflow or excessive memory usage might be a concern.
+----------------------------------+
| Use Recursion |
| +---------------------------+
| | Tree Traversals |
| +---------------------------+
| | Sorting (QuickSort, etc.) |
| +---------------------------+
| Avoid Recursion |
| +---------------------------+
| | High Memory Usage |
| +---------------------------+
| | Simple Loop Problems |
+----------------------------------+
Approach to Implement a Recursive Solution
3. How to Approach a Recursive Problem
- Identify the Problem: Understand the problem and determine if it can be broken down into smaller instances.
- Base Case: Identify the simplest case that can be solved directly.
- Recursive Case: Define the function in terms of itself using smaller instances of the same problem.
- Combine Results: Combine the results of the smaller instances to solve the original problem.
+-----------------------------------------+ | Identify Problem | +-----------------------------------------+ | Base Case | | +---------------------------------+ | | Simplest Case Solved Directly | | +---------------------------------+ | Recursive Case | | +---------------------------------+ | | Function Calls Itself | | +---------------------------------+ | Combine Results | | +---------------------------------+ | | Solve Original Problem | | +---------------------------------+ +-----------------------------------------+
Example: Factorial
4. Explanation and Example
Factorial Definition:
- The factorial of a non-negative integer
nis the product of all positive integers less than or equal ton. - 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)|
| +---------------------------+
+----------------------------------+
5. 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
Example: Fibonacci Numbers
6. 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)|
| +------------------------------+
+-------------------------------------+
7. 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
Example: Permutations
8. Explanation and Example
Permutations Definition:
- A permutation is a re-arrangement of elements in a particular order.
- For a given set of
nelements, there aren!(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 of an empty list (
+-----------------------------------------+
| permutations(lst) |
| +----------------------------------+
| | Base Case: |
| | permutations([]) = [[]] |
| +----------------------------------+
| | Recursive Case: |
| | For each element in lst: |
| | Recursively permute rest |
| | Combine with current element|
| +----------------------------------+
+-----------------------------------------+
9. 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])) # Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]Step by step code execution walkthrough provided here - https://parucodes.blogspot.com/2025/01/recursion-examples-for-beginners-step.html
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