Recursion Patterns
Base cases, recursive calls, memoization, and when recursion is the right tool
Free tier: read the explanation here. Upgrade to Pro for Drills, Speed challenges & Mastery badges.
UpgradeKnowledge Debt detected
You can study this freely — but your score may plateau if these foundations have gaps. The Mastery badge requires them to be solid.
Explanation
solves problems by breaking them into smaller versions of the same problem. Every recursive solution has two parts:
1. :base-case[The stopping condition — a simple input the function handles directly without calling itself] — when to stop (return directly, no recursion) 2. Recursive case — reduce the problem and call yourself
def factorial(n: int) -> int:
if n <= 1: return 1 # base case
return n * factorial(n - 1) # recursive caseThe call stack — what's actually happening:
factorial(4) → 4 * factorial(3) → 3 * factorial(2) → 2 * factorial(1) → 1 (base case) ← 2 * 1 = 2 ← 3 * 2 = 6 ← 4 * 6 = 24
Memoization — cache to avoid redundant calls:
python from functools import lru_cache @lru_cache(maxsize=None) def fibonacci(n: int) -> int: if n < 2: return n return fibonacci(n - 1) + fibonacci(n - 2) # Without cache: O(2ⁿ) — exponential # With cache: O(n) — each value computed once
Divide and conquer pattern:
python def binary_search(arr, target, lo=0, hi=None): if hi is None: hi = len(arr) - 1 if lo > hi: return -1 # base case: not found mid = (lo + hi) // 2 if arr[mid] == target: return mid if arr[mid] < target: return binary_search(arr, target, mid + 1, hi) return binary_search(arr, target, lo, mid - 1)
When to use recursion:
✓ Tree/graph traversal (naturally recursive structure) ✓ Divide-and-conquer (merge sort, binary search) ✓ Backtracking (permutations, combinations) ✗ Deep recursion on large inputs → stack overflow (use iteration instead) ✗ When iteration is just as clear (avoid cleverness for its own sake)
Examples
Flatten a nested list
Trees and nested structures are the natural home of recursion
def flatten(lst: list) -> list:
result = []
for item in lst:
if isinstance(item, list):
result.extend(flatten(item)) # recursive case
else:
result.append(item) # base case
return result
nested = [1, [2, [3, 4], 5], [6, 7]]
print(flatten(nested)) # [1, 2, 3, 4, 5, 6, 7]Backtracking — generate all permutations
Backtracking: choose an element, recurse on the rest, collect results
def permutations(nums: list[int]) -> list[list[int]]:
if len(nums) <= 1:
return [nums[:]]
result = []
for i in range(len(nums)):
# Choose nums[i] as first element
rest = nums[:i] + nums[i+1:]
for perm in permutations(rest):
result.append([nums[i]] + perm)
return result
print(permutations([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]How well did you understand this?
Next in Algorithms & Data Structures
Binary Search