Table of Contents
- Introduction to Recursion
- How Recursion Works
- Components of Recursion
- Types of Recursion
- Common Recursion Examples
- Recursion vs Iteration
- Recursion Depth and Stack Overflow
- Tail Recursion
- Advanced Recursion Patterns
- Real-World Applications
- Debugging Recursion
- Common Mistakes and Pitfalls
- Best Practices
Introduction to Recursion
Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller, similar subproblems. It's a powerful concept that allows you to write elegant solutions for problems that have a naturally recursive structure.
What is Recursion?
Think of recursion like Russian nesting dolls (Matryoshka dolls) - each doll contains a smaller version of itself until you reach the smallest doll.
# Simple analogy: Countdown
def countdown(n):
if n <= 0:
print("Blast off!")
else:
print(n)
countdown(n - 1) # Function calls itself
countdown(5)
# Output:
# 5
# 4
# 3
# 2
# 1
# Blast off!
The Recursive Mindset
Recursive Thinking: ├── Identify the base case (simplest version of the problem) ├── Identify the recursive case (how to reduce the problem) ├── Assume the recursive call works (trust the recursion) └── Combine results to solve the original problem
How Recursion Works
The Call Stack
When a function calls itself, each call is placed on the call stack.
def factorial(n):
print(f"Calling factorial({n})")
if n <= 1:
print(f"Base case: factorial(1) = 1")
return 1
else:
result = n * factorial(n - 1)
print(f"factorial({n}) = {n} * factorial({n-1}) = {result}")
return result
factorial(4)
Visual representation of call stack:
factorial(4) called ├── factorial(4) calls factorial(3) │ ├── factorial(3) calls factorial(2) │ │ ├── factorial(2) calls factorial(1) │ │ │ └── factorial(1) returns 1 │ │ └── factorial(2) returns 2 * 1 = 2 │ └── factorial(3) returns 3 * 2 = 6 └── factorial(4) returns 4 * 6 = 24
Step-by-Step Execution
# Let's trace factorial(4) step by step # Step 1: factorial(4) called # n = 4, not base case, so compute 4 * factorial(3) # Step 2: factorial(3) called # n = 3, not base case, so compute 3 * factorial(2) # Step 3: factorial(2) called # n = 2, not base case, so compute 2 * factorial(1) # Step 4: factorial(1) called # n = 1, BASE CASE REACHED! # factorial(1) returns 1 # Step 5: Back to factorial(2) # 2 * factorial(1) = 2 * 1 = 2 # factorial(2) returns 2 # Step 6: Back to factorial(3) # 3 * factorial(2) = 3 * 2 = 6 # factorial(3) returns 6 # Step 7: Back to factorial(4) # 4 * factorial(3) = 4 * 6 = 24 # factorial(4) returns 24
Components of Recursion
1. Base Case (Stopping Condition)
The base case is the condition that stops the recursion. Without it, recursion would continue indefinitely.
# ❌ Infinite recursion - NO BASE CASE
def infinite_recursion(n):
print(n)
return infinite_recursion(n - 1) # Never stops!
# ✅ Proper base case
def countdown(n):
if n <= 0: # Base case
print("Done!")
return
print(n)
countdown(n - 1) # Recursive case
2. Recursive Case
The recursive case reduces the problem toward the base case.
def sum_numbers(n): # Base case: sum of numbers from 1 to 1 is 1 if n == 1: return 1 # Recursive case: n + sum of numbers from 1 to n-1 return n + sum_numbers(n - 1)
3. Progress Toward Base Case
Each recursive call must move closer to the base case.
# ✅ Good - Progress toward base case def count_up(start, end): if start > end: return print(start) count_up(start + 1, end) # Moving forward # ❌ Bad - No progress (infinite recursion) def count_down_forever(n): print(n) count_down_forever(n) # Same value, never reaches base case
Types of Recursion
1. Direct Recursion
A function calls itself directly.
# Direct recursion def direct_recursion(n): if n <= 0: return print(n) direct_recursion(n - 1)
2. Indirect Recursion
Function A calls function B, which calls function A.
def function_a(n):
if n <= 0:
return
print(f"A: {n}")
function_b(n - 1)
def function_b(n):
if n <= 0:
return
print(f"B: {n}")
function_a(n - 1)
function_a(5)
# Output:
# A: 5
# B: 4
# A: 3
# B: 2
# A: 1
3. Linear Recursion
Each recursive call makes at most one additional recursive call.
def factorial(n): if n <= 1: return 1 return n * factorial(n - 1) # Single recursive call
4. Tree Recursion
A function makes multiple recursive calls (like in Fibonacci).
def fibonacci(n): if n <= 1: return n return fibonacci(n - 1) + fibonacci(n - 2) # Two recursive calls # Visual representation: # fibonacci(4) # ├── fibonacci(3) # │ ├── fibonacci(2) # │ │ ├── fibonacci(1) → 1 # │ │ └── fibonacci(0) → 0 # │ └── fibonacci(1) → 1 # └── fibonacci(2) # ├── fibonacci(1) → 1 # └── fibonacci(0) → 0 # Result: 3
5. Nested Recursion
Recursive function calls itself with a recursive argument.
def nested_recursion(n): if n > 100: return n - 10 return nested_recursion(nested_recursion(n + 11)) print(nested_recursion(95)) # 91
6. Mutual Recursion
Two or more functions call each other recursively.
def is_even(n): if n == 0: return True return is_odd(n - 1) def is_odd(n): if n == 0: return False return is_even(n - 1) print(is_even(4)) # True print(is_odd(5)) # True
Common Recursion Examples
1. Factorial
def factorial(n):
"""
Calculate n! = n * (n-1) * (n-2) * ... * 1
Time Complexity: O(n)
Space Complexity: O(n) due to call stack
"""
if n <= 1:
return 1
return n * factorial(n - 1)
# With memoization for better performance
factorial_cache = {}
def factorial_memo(n):
if n in factorial_cache:
return factorial_cache[n]
if n <= 1:
return 1
factorial_cache[n] = n * factorial_memo(n - 1)
return factorial_cache[n]
# Iterative version for comparison
def factorial_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
2. Fibonacci Sequence
def fibonacci(n):
"""
Calculate nth Fibonacci number: F(n) = F(n-1) + F(n-2)
where F(0) = 0, F(1) = 1
Time Complexity: O(2^n) - Very slow for large n
Space Complexity: O(n) due to call stack
"""
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
# Optimized with memoization
fib_cache = {}
def fibonacci_memo(n):
if n in fib_cache:
return fib_cache[n]
if n <= 1:
return n
fib_cache[n] = fibonacci_memo(n - 1) + fibonacci_memo(n - 2)
return fib_cache[n]
# Using lru_cache decorator (Python)
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci_cached(n):
if n <= 1:
return n
return fibonacci_cached(n - 1) + fibonacci_cached(n - 2)
3. Sum of Array
def sum_array(arr, n): """ Sum first n elements of an array Time Complexity: O(n) Space Complexity: O(n) """ if n <= 0: return 0 return arr[n - 1] + sum_array(arr, n - 1) # Alternative: sum from index to end def sum_array_range(arr, start): if start >= len(arr): return 0 return arr[start] + sum_array_range(arr, start + 1)
4. Binary Search
def binary_search(arr, target, left, right): """ Recursive binary search Time Complexity: O(log n) Space Complexity: O(log n) due to call stack """ if left > right: return -1 mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: return binary_search(arr, target, mid + 1, right) else: return binary_search(arr, target, left, mid - 1)
5. Tower of Hanoi
def tower_of_hanoi(n, source, auxiliary, destination):
"""
Solve Tower of Hanoi puzzle
Time Complexity: O(2^n)
Space Complexity: O(n)
"""
if n == 1:
print(f"Move disk 1 from {source} to {destination}")
return
# Move n-1 disks from source to auxiliary
tower_of_hanoi(n - 1, source, destination, auxiliary)
# Move largest disk from source to destination
print(f"Move disk {n} from {source} to {destination}")
# Move n-1 disks from auxiliary to destination
tower_of_hanoi(n - 1, auxiliary, source, destination)
# Usage
tower_of_hanoi(3, 'A', 'B', 'C')
# Output shows all moves to transfer 3 disks from A to C
6. Palindrome Check
def is_palindrome(s): """ Check if string is palindrome using recursion Time Complexity: O(n) Space Complexity: O(n) """ # Base case: empty string or single character is palindrome if len(s) <= 1: return True # Check first and last characters if s[0] != s[-1]: return False # Recursively check the substring without first and last characters return is_palindrome(s[1:-1]) # With index parameters (more efficient) def is_palindrome_range(s, left, right): if left >= right: return True if s[left] != s[right]: return False return is_palindrome_range(s, left + 1, right - 1)
7. Power Function
def power(base, exponent): """ Calculate base^exponent recursively Time Complexity: O(n) Space Complexity: O(n) """ if exponent == 0: return 1 if exponent < 0: return 1 / power(base, -exponent) return base * power(base, exponent - 1) # Optimized exponentiation (divide and conquer) def power_optimized(base, exponent): """ Calculate base^exponent using exponentiation by squaring Time Complexity: O(log n) Space Complexity: O(log n) """ if exponent == 0: return 1 if exponent < 0: return 1 / power_optimized(base, -exponent) if exponent % 2 == 0: half = power_optimized(base, exponent // 2) return half * half else: return base * power_optimized(base, exponent - 1)
Recursion vs Iteration
Comparison Table
| Aspect | Recursion | Iteration |
|---|---|---|
| Concept | Function calls itself | Loop repeats code |
| Memory | Uses call stack (more memory) | Uses fixed memory |
| Speed | Slower (function call overhead) | Faster |
| Code | Often more elegant, readable | Can be verbose |
| Risk | Stack overflow | Infinite loop |
| Use Cases | Tree structures, divide & conquer | Simple loops, large iterations |
Converting Recursion to Iteration
# Recursive factorial def factorial_recursive(n): if n <= 1: return 1 return n * factorial_recursive(n - 1) # Iterative factorial def factorial_iterative(n): result = 1 for i in range(1, n + 1): result *= i return result # Recursive binary tree traversal def inorder_traversal(node): if node: inorder_traversal(node.left) print(node.value) inorder_traversal(node.right) # Iterative binary tree traversal (using stack) def inorder_traversal_iterative(root): stack = [] current = root while stack or current: while current: stack.append(current) current = current.left current = stack.pop() print(current.value) current = current.right
When to Use Recursion vs Iteration
Use Recursion When: ├── Problem has natural recursive structure ├── Working with tree/graph structures ├── Divide and conquer algorithms ├── Depth-first search ├── Backtracking problems └── Code clarity is more important than performance Use Iteration When: ├── Simple loops with known iteration count ├── Performance is critical ├── Risk of deep recursion (stack overflow) ├── Processing large datasets └── When recursion would be unnecessarily complex
Recursion Depth and Stack Overflow
Understanding Stack Overflow
Each recursive call adds a new frame to the call stack. Too many calls can cause a stack overflow.
import sys
def deep_recursion(n):
if n == 0:
return
deep_recursion(n - 1)
# This will cause RecursionError for large n
try:
deep_recursion(10000) # May exceed recursion limit
except RecursionError as e:
print(f"Error: {e}")
Recursion Limit
import sys # Check current recursion limit print(sys.getrecursionlimit()) # Usually 1000 # Increase recursion limit (use with caution) sys.setrecursionlimit(10000) # Now we can go deeper def deep_recursion(n): if n == 0: return deep_recursion(n - 1) deep_recursion(5000) # Works, but not recommended
Managing Deep Recursion
# 1. Convert to iteration for deep recursion def factorial_iterative(n): result = 1 for i in range(1, n + 1): result *= i return result # 2. Use tail recursion optimization (if supported) def factorial_tail(n, accumulator=1): if n <= 1: return accumulator return factorial_tail(n - 1, n * accumulator) # 3. Use memoization to reduce recursion depth from functools import lru_cache @lru_cache(maxsize=None) def fibonacci_cached(n): if n <= 1: return n return fibonacci_cached(n - 1) + fibonacci_cached(n - 2)
Tail Recursion
What is Tail Recursion?
Tail recursion occurs when the recursive call is the last operation in the function.
# NOT tail recursive (multiplication happens after recursive call) def factorial_not_tail(n): if n <= 1: return 1 return n * factorial_not_tail(n - 1) # Multiplication after call # Tail recursive (nothing after recursive call) def factorial_tail(n, accumulator=1): if n <= 1: return accumulator return factorial_tail(n - 1, n * accumulator) # Call is last operation
Tail Call Optimization (TCO)
Some languages (like Scheme, Haskell) optimize tail recursion to avoid stack growth.
# Python does NOT support tail call optimization # Each call still adds to stack # However, we can simulate with trampoline def trampoline(f): def wrapper(*args): result = f(*args) while callable(result): result = result() return result return wrapper @trampoline def factorial_tco(n, accumulator=1): if n <= 1: return accumulator return lambda: factorial_tco(n - 1, n * accumulator) print(factorial_tco(1000)) # Works without recursion error
Advanced Recursion Patterns
1. Backtracking
Backtracking is a form of recursion that builds candidates and abandons them when they can't lead to a solution.
def solve_n_queens(n):
"""Place N queens on NxN chessboard so no two attack each other"""
solutions = []
def is_safe(board, row, col):
# Check column
for i in range(row):
if board[i] == col:
return False
# Check diagonals
if abs(board[i] - col) == abs(i - row):
return False
return True
def backtrack(board, row):
if row == n:
solutions.append(board[:])
return
for col in range(n):
if is_safe(board, row, col):
board[row] = col
backtrack(board, row + 1)
# Backtrack - no need to reset board as it will be overwritten
backtrack([-1] * n, 0)
return solutions
# Generate all solutions for 4-queens
solutions = solve_n_queens(4)
print(f"Found {len(solutions)} solutions")
2. Divide and Conquer
def merge_sort(arr): """ Divide and conquer sorting algorithm Time Complexity: O(n log n) Space Complexity: O(n) """ if len(arr) <= 1: return arr # Divide mid = len(arr) // 2 left = merge_sort(arr[:mid]) right = merge_sort(arr[mid:]) # Conquer (merge) return merge(left, right) def merge(left, right): result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result.extend(left[i:]) result.extend(right[j:]) return result
3. Memoization (Dynamic Programming)
def coin_change(coins, amount):
"""
Find minimum number of coins to make amount
Time Complexity: O(amount * len(coins))
Space Complexity: O(amount)
"""
memo = {}
def dp(remaining):
if remaining == 0:
return 0
if remaining < 0:
return float('inf')
if remaining in memo:
return memo[remaining]
min_coins = float('inf')
for coin in coins:
result = dp(remaining - coin)
if result != float('inf'):
min_coins = min(min_coins, result + 1)
memo[remaining] = min_coins
return min_coins
result = dp(amount)
return result if result != float('inf') else -1
4. Recursive Descent Parsing
class ExpressionParser:
"""Simple arithmetic expression parser using recursion"""
def parse(self, expression):
self.tokens = expression.replace(' ', '')
self.pos = 0
return self.parse_expression()
def parse_expression(self):
result = self.parse_term()
while self.pos < len(self.tokens):
if self.tokens[self.pos] == '+':
self.pos += 1
result += self.parse_term()
elif self.tokens[self.pos] == '-':
self.pos += 1
result -= self.parse_term()
else:
break
return result
def parse_term(self):
result = self.parse_factor()
while self.pos < len(self.tokens):
if self.tokens[self.pos] == '*':
self.pos += 1
result *= self.parse_factor()
elif self.tokens[self.pos] == '/':
self.pos += 1
result /= self.parse_factor()
else:
break
return result
def parse_factor(self):
if self.tokens[self.pos] == '(':
self.pos += 1
result = self.parse_expression()
self.pos += 1 # Skip ')'
return result
else:
return self.parse_number()
def parse_number(self):
start = self.pos
while self.pos < len(self.tokens) and self.tokens[self.pos].isdigit():
self.pos += 1
return int(self.tokens[start:self.pos])
# Usage
parser = ExpressionParser()
result = parser.parse("(3 + 5) * 2 - 4")
print(result) # 12
Real-World Applications
1. File System Traversal
import os
def list_all_files(directory, indent=0):
"""
Recursively list all files in directory tree
"""
try:
items = os.listdir(directory)
except PermissionError:
return
for item in sorted(items):
path = os.path.join(directory, item)
print(" " * indent + f"📁 {item}" if os.path.isdir(path) else " " * indent + f"📄 {item}")
if os.path.isdir(path):
list_all_files(path, indent + 1)
# Usage
list_all_files("/home/user/projects")
2. Directory Size Calculator
import os
def calculate_directory_size(path):
"""
Recursively calculate total size of directory in bytes
"""
total = 0
try:
items = os.listdir(path)
except PermissionError:
return 0
for item in items:
item_path = os.path.join(path, item)
if os.path.isfile(item_path):
total += os.path.getsize(item_path)
elif os.path.isdir(item_path):
total += calculate_directory_size(item_path)
return total
def format_size(bytes_size):
for unit in ['B', 'KB', 'MB', 'GB', 'TB']:
if bytes_size < 1024:
return f"{bytes_size:.1f} {unit}"
bytes_size /= 1024
return f"{bytes_size:.1f} PB"
# Usage
size = calculate_directory_size("/home/user/Documents")
print(f"Directory size: {format_size(size)}")
3. Web Crawler (Simple)
import requests
from urllib.parse import urljoin, urlparse
class SimpleCrawler:
def __init__(self, max_depth=3):
self.visited = set()
self.max_depth = max_depth
def crawl(self, url, depth=0):
if depth > self.max_depth or url in self.visited:
return
print(f"Crawling: {url} (depth {depth})")
self.visited.add(url)
try:
response = requests.get(url, timeout=5)
if response.status_code != 200:
return
# Extract links (simplified)
content = response.text
start = 0
while True:
link_start = content.find('href="', start)
if link_start == -1:
break
link_start += 6
link_end = content.find('"', link_start)
if link_end == -1:
break
link = content[link_start:link_end]
absolute_link = urljoin(url, link)
# Only crawl same domain
if urlparse(absolute_link).netloc == urlparse(url).netloc:
self.crawl(absolute_link, depth + 1)
start = link_end
except Exception as e:
print(f"Error crawling {url}: {e}")
# Usage (careful with real websites!)
# crawler = SimpleCrawler(max_depth=2)
# crawler.crawl("https://example.com")
4. JSON Processing
import json
def find_values(data, target_key):
"""
Recursively find all values for a given key in nested JSON
"""
results = []
if isinstance(data, dict):
for key, value in data.items():
if key == target_key:
results.append(value)
else:
results.extend(find_values(value, target_key))
elif isinstance(data, list):
for item in data:
results.extend(find_values(item, target_key))
return results
def transform_json(data, transform_func):
"""
Recursively transform all values in nested JSON
"""
if isinstance(data, dict):
return {k: transform_json(v, transform_func) for k, v in data.items()}
elif isinstance(data, list):
return [transform_json(item, transform_func) for item in data]
else:
return transform_func(data)
# Usage
data = {
"name": "John",
"address": {
"city": "New York",
"zip": "10001"
},
"tags": ["developer", "python", "programmer"]
}
# Find all values with key "city"
cities = find_values(data, "city")
print(cities) # ['New York']
# Uppercase all strings
uppercase_data = transform_json(data, lambda x: x.upper() if isinstance(x, str) else x)
print(uppercase_data)
Debugging Recursion
Print Debugging
def fibonacci_debug(n, depth=0):
indent = " " * depth
print(f"{indent}fibonacci({n}) called")
if n <= 1:
print(f"{indent}Return {n}")
return n
result = fibonacci_debug(n - 1, depth + 1) + fibonacci_debug(n - 2, depth + 1)
print(f"{indent}Return {result}")
return result
fibonacci_debug(4)
Using a Debugger
import pdb def factorial_debug(n): if n <= 1: return 1 # Set breakpoint pdb.set_trace() return n * factorial_debug(n - 1) # Run with: # factorial_debug(5) # Then use commands: # - n (next line) # - s (step into) # - c (continue) # - p variable (print variable) # - q (quit)
Visualizing Recursion Tree
def print_recursion_tree(n, prefix="", is_last=True):
print(prefix + ("└── " if is_last else "├── ") + f"fib({n})")
if n <= 1:
return
child_prefix = prefix + (" " if is_last else "│ ")
# Print left child (n-1)
print_recursion_tree(n - 1, child_prefix, False)
# Print right child (n-2)
print_recursion_tree(n - 2, child_prefix, True)
print_recursion_tree(4)
Common Mistakes and Pitfalls
1. Missing Base Case
# ❌ No base case - infinite recursion def factorial_wrong(n): return n * factorial_wrong(n - 1) # Never stops! # ✅ With base case def factorial_correct(n): if n <= 1: return 1 return n * factorial_correct(n - 1)
2. Not Progressing Toward Base Case
# ❌ Not progressing def countdown_wrong(n): if n <= 0: return print(n) countdown_wrong(n) # Same value! # ✅ Progressing def countdown_correct(n): if n <= 0: return print(n) countdown_correct(n - 1) # Decreasing
3. Recomputing Same Values (Fibonacci)
# ❌ Exponential recomputation
def fibonacci_slow(n):
if n <= 1:
return n
return fibonacci_slow(n - 1) + fibonacci_slow(n - 2) # Repeats calculations
# ✅ With memoization
fib_cache = {}
def fibonacci_fast(n):
if n in fib_cache:
return fib_cache[n]
if n <= 1:
return n
fib_cache[n] = fibonacci_fast(n - 1) + fibonacci_fast(n - 2)
return fib_cache[n]
4. Stack Overflow
# ❌ May cause stack overflow def sum_large_range(n): if n <= 0: return 0 return n + sum_large_range(n - 1) # ✅ Use iteration for large n def sum_large_range_iterative(n): return n * (n + 1) // 2 # O(1) formula
5. Unnecessary Recursion
# ❌ Overly complex recursion def power(base, exponent): if exponent == 0: return 1 return base * power(base, exponent - 1) # Works but inefficient # ✅ Use built-in or iterative result = base ** exponent
Best Practices
1. Always Have a Base Case
def recursive_function(params): # Base case first (stopping condition) if base_case_condition: return base_result # Recursive case return recursive_function(smaller_params)
2. Ensure Progress Toward Base Case
def process_list(lst, index=0): # Base case if index >= len(lst): return # Process current element print(lst[index]) # Move toward base case (index increases) process_list(lst, index + 1)
3. Use Memoization for Repeated Calculations
from functools import lru_cache @lru_cache(maxsize=None) def expensive_recursive_function(n): if n <= 1: return n return expensive_recursive_function(n - 1) + expensive_recursive_function(n - 2)
4. Consider Tail Recursion
# Tail recursive version (if language supports TCO) def factorial_tail(n, accumulator=1): if n <= 1: return accumulator return factorial_tail(n - 1, n * accumulator)
5. Use Recursion for Natural Recursive Structures
# Good for tree traversal def traverse_tree(node): if not node: return traverse_tree(node.left) print(node.value) traverse_tree(node.right)
6. Document Recursive Functions
def binary_search(arr, target, left, right): """ Recursive binary search. Base case: left > right (target not found) Recursive case: search left or right half based on comparison Args: arr: Sorted list to search target: Value to find left: Left boundary index right: Right boundary index Returns: Index of target if found, else -1 """ if left > right: return -1 mid = (left + right) // 2 if arr[mid] == target: return mid elif arr[mid] < target: return binary_search(arr, target, mid + 1, right) else: return binary_search(arr, target, left, mid - 1)
7. Limit Recursion Depth
import sys
def safe_recursion(func):
"""Decorator to handle recursion depth errors"""
def wrapper(*args, **kwargs):
try:
return func(*args, **kwargs)
except RecursionError:
print(f"Error: Recursion depth exceeded in {func.__name__}")
return None
return wrapper
@safe_recursion
def deep_recursion(n):
if n <= 0:
return
deep_recursion(n - 1)
deep_recursion(10000) # Will handle error gracefully
Conclusion
Key Takeaways
- Recursion is about breaking problems into smaller, similar subproblems
- Every recursive function needs:
- Base case (stopping condition)
- Recursive case (progress toward base case)
- Recursion is elegant but has costs:
- Memory overhead (call stack)
- Function call overhead
- Risk of stack overflow
- When to use recursion:
- Tree/graph traversal
- Divide and conquer algorithms
- Problems with natural recursive structure
- When code clarity outweighs performance concerns
Recursion Checklist
✓ Base case defined ✓ Progress toward base case ✓ Handles edge cases ✓ Considered stack depth ✓ Considered memoization for repeated calculations ✓ Considered iterative alternative ✓ Properly documented
Practice Problems
Start with these classic recursion problems:
- Factorial
- Fibonacci
- Binary search
- Tower of Hanoi
- Merge sort
- Quick sort
- Tree traversal
- Permutations
- Subset generation
- Maze solving
Recursion is a powerful tool that, when used correctly, can produce elegant solutions to complex problems. Master it, and you'll have a valuable addition to your programming toolkit!