Recursion is a programming technique where a function calls itself to solve a smaller version of the same problem — until it reaches a base condition (a stopping point).
In Python, recursion is often used for tasks that can be broken down into smaller subproblems, like:
- Factorial calculation
- Fibonacci sequence
- Searching or sorting
- Tree traversal
- Reversing a list (our example) ✅
Let’s learn recursion step-by-step by reversing a list 👇
🔹 1. What is Recursion?
A recursive function:
- Calls itself.
- Has a base condition to stop infinite recursion.
- Reduces the problem size in each recursive call.
✅ Basic Syntax:
def recursive_function():
if base_condition:
return result
else:
return recursive_function(smaller_input)🔹 2. Example Problem — Reverse a List
We want to reverse a list without using any built-in functions like reverse() or slicing ([::-1]).
Example Input:
[1, 2, 3, 4, 5]Expected Output:
[5, 4, 3, 2, 1]🔹 3. Recursive Approach — Step by Step
🧠 Idea:
To reverse a list recursively:
- Base case: If the list is empty or has one element → return it as is.
- Recursive step: Take the first element, call the function for the rest of the list, and then append the first element at the end.
✅ Implementation:
def reverse_list(lst):
# Base Case
if len(lst) <= 1:
return lst
# Recursive Case
return reverse_list(lst[1:]) + [lst[0]]
# Example
my_list = [1, 2, 3, 4, 5]
print("Original List:", my_list)
print("Reversed List:", reverse_list(my_list))Output:
Original List: [1, 2, 3, 4, 5]
Reversed List: [5, 4, 3, 2, 1]🔹 4. Step-by-Step Execution (Recursive Trace)
Let’s trace how recursion works internally for [1, 2, 3, 4, 5] 👇
| Call | lst | Action |
|---|---|---|
| 1 | [1, 2, 3, 4, 5] | Calls reverse_list([2, 3, 4, 5]) |
| 2 | [2, 3, 4, 5] | Calls reverse_list([3, 4, 5]) |
| 3 | [3, 4, 5] | Calls reverse_list([4, 5]) |
| 4 | [4, 5] | Calls reverse_list([5]) |
| 5 | [5] | Base case → returns [5] |
| 4 return | [5] + [4] → [5, 4] | |
| 3 return | [5, 4] + [3] → [5, 4, 3] | |
| 2 return | [5, 4, 3] + [2] → [5, 4, 3, 2] | |
| 1 return | [5, 4, 3, 2] + [1] → [5, 4, 3, 2, 1] |
✅ The function unwinds back up the call stack, building the reversed list step by step.
🔹 5. Visualization of Recursion Tree
reverse_list([1,2,3,4,5])
→ reverse_list([2,3,4,5]) + [1]
→ reverse_list([3,4,5]) + [2]
→ reverse_list([4,5]) + [3]
→ reverse_list([5]) + [4]
→ [5] (base case)Then results are combined:
[5] + [4] → [5,4]
[5,4] + [3] → [5,4,3]
[5,4,3] + [2] → [5,4,3,2]
[5,4,3,2] + [1] → [5,4,3,2,1]✅ Final Result: [5, 4, 3, 2, 1]
🔹 6. Example 2 — Using an Index-Based Recursive Approach
You can also reverse a list in-place using recursion with index swapping.
✅ Implementation:
def reverse_in_place(lst, start=0, end=None):
if end is None:
end = len(lst) - 1
# Base case: stop when start >= end
if start >= end:
return
# Swap elements
lst[start], lst[end] = lst[end], lst[start]
# Recursive call
reverse_in_place(lst, start + 1, end - 1)
# Example
numbers = [10, 20, 30, 40, 50]
print("Before Reversing:", numbers)
reverse_in_place(numbers)
print("After Reversing:", numbers)Output:
Before Reversing: [10, 20, 30, 40, 50]
After Reversing: [50, 40, 30, 20, 10]✅ Here, recursion swaps the first and last elements and moves inward until the list is reversed.
🔹 7. Base Case Importance
If you forget to include a base case, recursion will continue infinitely until a RecursionError occurs.
def infinite_recursion():
print("Calling again...")
infinite_recursion()
# infinite_recursion() # ❌ Causes RecursionErrorOutput:
RecursionError: maximum recursion depth exceeded✅ Always define a base case to stop recursion.
🔹 8. Comparing Recursive vs Iterative Approach
| Approach | Method | Code Simplicity | Performance |
|---|---|---|---|
| Recursive | Function calls itself | Elegant, concise | Slower (due to call stack) |
| Iterative | Uses loop (for, while) | Slightly longer | Faster, memory-efficient |
Iterative Example:
lst = [1, 2, 3, 4, 5]
reversed_list = []
for i in range(len(lst) - 1, -1, -1):
reversed_list.append(lst[i])
print(reversed_list)Output:
[5, 4, 3, 2, 1]✅ Iteration avoids the call stack overhead but recursion is more elegant conceptually.
🧾 Summary Table
| Concept | Explanation |
|---|---|
| Recursion | Function calling itself until base case |
| Base Case | Stopping condition to prevent infinite calls |
| Recursive Case | Function calling itself with smaller input |
| Advantages | Elegant, easier for problems like trees or nested data |
| Disadvantages | Slower and memory-heavy due to call stack |
| Example Task | Reversing a list using recursion |
✅ In short:
Recursion works by breaking a problem into smaller versions of itself until it reaches a simple base case.
To reverse a list recursively, we call the function on the rest of the list and append the first element at the end each time.
🧩 Final Code Summary
def reverse_list(lst):
if len(lst) <= 1: # Base case
return lst
return reverse_list(lst[1:]) + [lst[0]]
print(reverse_list([1, 2, 3, 4, 5]))Output:
[5, 4, 3, 2, 1]✅ Conclusion:
Recursion allows elegant solutions like list reversal by breaking down the problem and combining results as the function unwinds.