Recursion is a programming method where a function calls itself to tackle smaller parts of a bigger problem. In Python, it is often used for tasks that can be divided into similar, smaller problems. Here are some typical examples of recursion in Python.
1. Factorial Calculation
A classic example of recursion is calculating the factorial of a number.
def factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n - 1)
# Example usage
print(factorial(5)) # Output: 120
2. Fibonacci Sequence
The Fibonacci sequence is another well-known problem solved using recursion.
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
# Example usage
print(fibonacci(6)) # Output: 8
3. Sum of a List
Recursion can be used to calculate the sum of elements in a list.
def recursive_sum(lst):
if not lst: # Base case: if the list is empty
return 0
else:
return lst[0] + recursive_sum(lst[1:])
# Example usage
print(recursive_sum([1, 2, 3, 4, 5])) # Output: 15
4. Traversing Nested Data Structures (e.g., Nested Lists or Dictionaries)
Recursion helps traverse or flatten nested data structures like lists or dictionaries.
Traversing Nested Lists:
def traverse_list(lst):
for element in lst:
if isinstance(element, list):
traverse_list(element)
else:
print(element)
# Example usage
nested_list = [1, [2, 3, [4, 5]], 6]
traverse_list(nested_list) # Output: 1 2 3 4 5 6
Traversing Nested Dictionaries:
def traverse_dict(d):
for key, value in d.items():
if isinstance(value, dict):
traverse_dict(value)
else:
print(f"{key}: {value}")
# Example usage
nested_dict = {
'a': 1,
'b': {'x': 10, 'y': {'z': 20}},
'c': 3
}
traverse_dict(nested_dict)
# Output:
# a: 1
# x: 10
# z: 20
# c: 3
5. Binary Search
Recursion can be used to implement binary search, an efficient algorithm for searching sorted lists.
def binary_search(arr, target, low, high):
if low > high:
return -1 # Target not found
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search(arr, target, mid + 1, high)
else:
return binary_search(arr, target, low, mid - 1)
# Example usage
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(binary_search(arr, 5, 0, len(arr) - 1)) # Output: 4
6. Tower of Hanoi Problem
This is a classic recursion problem. The goal is to move a set of disks from one rod to another while following certain rules.
def hanoi(n, source, destination, auxiliary):
if n == 1:
print(f"Move disk 1 from {source} to {destination}")
else:
hanoi(n - 1, source, auxiliary, destination)
print(f"Move disk {n} from {source} to {destination}")
hanoi(n - 1, auxiliary, destination, source)
# Example usage
hanoi(3, 'A', 'C', 'B')
# Output:
# Move disk 1 from A to C
# Move disk 2 from A to B
# Move disk 1 from C to B
# Move disk 3 from A to C
# Move disk 1 from B to A
# Move disk 2 from B to C
# Move disk 1 from A to C
7. Permutations of a String or List
Recursion is often used to generate all permutations of a string or list.
def permutations(s):
if len(s) == 1:
return [s]
else:
result = []
for i in range(len(s)):
for p in permutations(s[:i] + s[i+1:]):
result.append(s[i] + p)
return result
# Example usage
print(permutations("abc")) # Output: ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']
8. Solving Maze Problems
Recursion is used to explore possible paths in a maze. This approach can be adapted to a wide variety of problems that involve pathfinding.
def solve_maze(maze, x, y, solution):
# Base case: reached the destination
if x == len(maze) - 1 and y == len(maze[0]) - 1 and maze[x][y] == 1:
solution[x][y] = 1
return True
# Check if maze[x][y] is valid
if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 1:
solution[x][y] = 1
# Move right
if solve_maze(maze, x, y + 1, solution):
return True
# Move down
if solve_maze(maze, x + 1, y, solution):
return True
# If none of the above worked, backtrack
solution[x][y] = 0
return False
return False
# Example usage
maze = [
[1, 0, 0, 0],
[1, 1, 0, 1],
[0, 1, 0, 0],
[1, 1, 1, 1]
]
solution = [[0 for _ in range(len(maze[0]))] for _ in range(len(maze))]
solve_maze(maze, 0, 0, solution)
for row in solution:
print(row)
# Output (solution path):
# [1, 0, 0, 0]
# [1, 1, 0, 0]
# [0, 1, 0, 0]
# [0, 1, 1, 1]
9. Tree Traversals
Recursion is widely used in tree data structures for traversing trees (in-order, pre-order, post-order).
class Node:
def __init__(self, value):
self.left = None
self.right = None
self.value = value
def in_order_traversal(root):
if root:
in_order_traversal(root.left)
print(root.value, end=" ")
in_order_traversal(root.right)
# Example usage
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
in_order_traversal(root) # Output: 4 2 5 1 3
10. Divide and Conquer Algorithms
Recursion is fundamental in divide and conquer algorithms, like merge sort or quicksort.
Merge Sort:
def merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2left_half = arr[:mid]right_half = arr[mid:]merge_sort(left_half)merge_sort(right_half)i = j = k = 0while i < len(left_half) and j < len(right_half):if left_half[i] < right_half[j]:arr[k] = left_half[i]i += 1else:arr[k] = right_half[j]j += 1k += 1while i < len(left_half):arr[k] = left_half[i]i += 1k += 1while j < len(right_half):arr[k] = right_half[j]j += 1k += 1# Example usagearr = [38, 27, 43, 3, 9, 82, 10]merge_sort(arr)print(arr) # Output: [3, 9, 10, 27, 38, 43, 82]
Also, read: Top Books Data Engineering Code Pipelines
Key Takeaways:
- Breaking down problems: Recursion is useful for issues that can be divided into smaller subproblems.
- Base case: Every recursive function should have a base case to prevent infinite recursion.
- Efficiency: Recursion can make some problems easier to conceptualize. However, it is not always the most efficient solution. This is due to potential overhead in function calls and space complexity.
