pythonalgorithmsrecursion
Understanding Recursion
Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem.
Why Recursion?
Recursive solutions are elegant and can simplify complex problems. They're ideal for:
- Tree traversals - navigating hierarchical data
- Divide and conquer - breaking problems into smaller sub-problems
- Mathematical sequences - factorial, fibonacci, etc.
python
# Your first recursive function: Factorial
def factorial(n):
"""Calculate n! (n factorial)"""
# Base case: stop condition
if n <= 1:
return 1
# Recursive case: call itself with smaller problem
return n * factorial(n - 1)
# Test it
print(f"5! = {factorial(5)}") # 120
print(f"0! = {factorial(0)}") # 1How It Works
When factorial(5) is called:
factorial(5)
→ 5 * factorial(4)
→ 4 * factorial(3)
→ 3 * factorial(2)
→ 2 * factorial(1)
→ 1 (base case)
→ 2 * 1 = 2
→ 3 * 2 = 6
→ 4 * 6 = 24
→ 5 * 24 = 120
Every recursive function needs:
- Base case - when to stop
- Recursive case - how to break down the problem
python
# Fibonacci Sequence
def fibonacci(n):
"""Return the nth Fibonacci number"""
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
# Print first 10 Fibonacci numbers
for i in range(10):
print(f"fib({i}) = {fibonacci(i)}")Recursive vs Iterative
Let's compare both approaches for summing a list:
python
# Iterative approach
def sum_list_iterative(arr):
total = 0
for num in arr:
total += num
return total
# Recursive approach
def sum_list_recursive(arr):
if len(arr) == 0:
return 0
return arr[0] + sum_list_recursive(arr[1:])
# Test both
numbers = [1, 2, 3, 4, 5]
print(f"Iterative: {sum_list_iterative(numbers)}")
print(f"Recursive: {sum_list_recursive(numbers)}")Exercise 1: Reverse a String
Write a recursive function that reverses a string.
Expected output:
reverse_string("hello") → "olleh"
reverse_string("Python") → "nohtyP"
python
# Exercise 1: Your code here
def reverse_string(s):
# TODO: Implement recursively
pass
# Test your implementation
# Uncomment when ready:
# print(reverse_string("hello")) # olleh
# print(reverse_string("Python")) # nohtyPExercise 2: Count Items in Nested List
Write a recursive function that counts all elements in a nested list.
Example:
python
nested = [1, [2, [3, 4]], 5]
count_all(nested) # Returns 5python
# Exercise 2: Your code here
def count_all(lst):
# TODO: Count all items including in nested lists
pass
# Test your implementation
# Uncomment when ready:
# nested = [1, [2, [3, 4]], 5]
# print(count_all(nested)) # 5Exercise 3: Power Function
Implement power(base, exp) using recursion (don't use ** operator).
Expected output:
power(2, 3) → 8
power(5, 2) → 25
power(2, 0) → 1
python
# Exercise 3: Your code here
def power(base, exp):
# TODO: Implement using recursion
pass
# Test your implementation
# Uncomment when ready:
# print(power(2, 3)) # 8
# print(power(5, 2)) # 25
# print(power(2, 0)) # 1Common Pitfalls
- Missing base case → infinite recursion (stack overflow)
- Forgetting to return in the recursive case
- Not reducing the problem sufficiently with each call
python
# BAD: No base case!
def bad_recursion(n):
return n * bad_recursion(n - 1) # Crashes!Always test your base case first!
python
# Challenge: Check if a string is a palindrome
def is_palindrome(s):
"""
Check if string s is a palindrome (reads same forwards and backwards)
Ignore spaces and case.
Examples:
- "racecar" → True
- "hello" → False
- "A man a plan a canal Panama" → True
"""
# TODO: Implement recursively
pass
# Test
# print(is_palindrome("racecar")) # True
# print(is_palindrome("hello")) # False
# print(is_palindrome("A man a plan a canal Panama")) # True