Basic Recursion

Understand the fundamental technique of solving problems by having functions call themselves. Master base cases, recursive cases, and the call stack to build the foundation for trees, graphs, and dynamic programming.

Time: O(n) for linear, O(2^n) for binary without memoization

Space: O(n) call stack depth for linear recursion

Learn & Reference

Understanding the Pattern

Basic Recursion

Recursion is when a function calls itself to solve a smaller version of the same problem. It's not just a technique — it's a way of thinking. Many data structures (trees, graphs, nested lists) are inherently recursive, making recursion the natural approach.

The Two Essential Parts

Base Case

The condition where the recursion stops. Without it, you get infinite recursion and a stack overflow. The base case handles the simplest possible input directly, without making a recursive call.

Recursive Case

The part where the function calls itself with a "smaller" input — closer to the base case. Each recursive call must make progress toward the base case, or the recursion will never terminate.

How It Works: The Call Stack

Each recursive call creates a new frame on the call stack with its own local variables. When a base case is reached, the stack starts "unwinding" — each frame returns its result to the caller above it.

Common Patterns

Accumulate

Build up a result as you recurse: sums, products, concatenated strings. Pass the accumulated value as a parameter or return it.

Divide and Conquer

Split the problem in half, solve each half recursively, then combine. This is how merge sort and binary search work.

Build Up

Start from the base case and construct the solution on the way back up the call stack. Each level adds one piece to the result.

Generate All Possibilities

Recursion naturally explores all branches of a decision tree. This is the basis for permutations, combinations, and backtracking.

Recursion vs Iteration

Every recursive solution can be rewritten iteratively (and vice versa). Recursion is clearer for tree/graph traversal and divide-and-conquer. Iteration is usually more memory-efficient since it avoids call stack overhead.

Common Mistakes

Missing base case: Without a stopping condition, recursion runs forever (stack overflow)
Base case doesn't cover all terminal states: Make sure edge cases like empty input, zero, and negative values are handled
Not making progress: Each recursive call must move closer to the base case. f(n) calling f(n) is an infinite loop
Stack overflow on large inputs: Deep recursion (10,000+ levels) can exceed the call stack. Consider iteration or tail-call optimization
Redundant computation: Naive recursion (like fibonacci) recalculates the same values. Use memoization or convert to iteration

When to Use

A problem that naturally breaks into smaller subproblems

Tree or nested data structures

Generate all problems (permutations, subsets)

Mathematical recurrences (factorial, fibonacci, power)

Problems where the solution depends on solutions to smaller inputs

Divide-and-conquer opportunities

Template

1# Basic Recursion
2# 1. Define the base case (when to stop)
3# 2. Define the recursive case (call self with smaller input)
4
5def solve(n):
6    if n <= 0:       # base case
7        return 0
8    return n + solve(n - 1)  # recursive case

{ }

Syntax Reference

1# === Basic recursive function ===
2def factorial(n):
3    if n <= 1:           # base case
4        return 1
5    return n * factorial(n - 1)  # recursive case
6
7# === Multiple base cases ===
8def fibonacci(n):
9    if n <= 0: return 0
10    if n == 1: return 1
11    return fibonacci(n - 1) + fibonacci(n - 2)
12
13# === Recursion with accumulator ===
14def sum_list(arr, index=0):
15    if index == len(arr):
16        return 0
17    return arr[index] + sum_list(arr, index + 1)
18
19# === Recursion limit ===
20import sys
21sys.getrecursionlimit()         # default ~1000
22sys.setrecursionlimit(10000)    # increase if needed
23
24# === Memoization ===
25from functools import lru_cache
26@lru_cache(maxsize=None)
27def fib(n):
28    if n <= 1: return n
29    return fib(n-1) + fib(n-2)

📋

Common Recipes

1# --- Recursive Sum ---
2def recursive_sum(arr):
3    if not arr:
4        return 0
5    return arr[0] + recursive_sum(arr[1:])
6
7# --- Recursive Reverse ---
8def reverse_string(s):
9    if len(s) <= 1:
10        return s
11    return reverse_string(s[1:]) + s[0]
12
13# --- Power Function ---
14def power(base, exp):
15    if exp == 0:
16        return 1
17    if exp % 2 == 0:
18        half = power(base, exp // 2)
19        return half * half
20    return base * power(base, exp - 1)
21
22# --- Flatten Nested List ---
23def flatten(arr):
24    result = []
25    for item in arr:
26        if isinstance(item, list):
27            result.extend(flatten(item))
28        else:
29            result.append(item)
30    return result

O(n)

Complexity

Pattern	Time	Space (Stack)	Notes
Linear recursion (n calls)	O(n)	O(n)	e.g., factorial, sum
Binary recursion (2 calls/level)	O(2^n)	O(n)	e.g., naive fibonacci
Binary recursion + memo	O(n)	O(n)	Each subproblem computed once
Divide and conquer	O(n log n)	O(log n)	e.g., merge sort
Generate permutations	O(n!)	O(n)	n! leaves in the recursion tree
Binary search (recursive)	O(log n)	O(log n)	Halves input each call

Watch Out

✗Missing base case: Without a stopping condition, recursion runs forever (stack overflow)
✗Base case doesn't cover all terminal states: Make sure edge cases like empty input, zero, and negative values are handled
✗Not making progress: Each recursive call must move closer to the base case. `f(n)` calling `f(n)` is an infinite loop
✗Stack overflow on large inputs: Deep recursion (10,000+ levels) can exceed the call stack. Consider iteration or tail-call optimization
✗Redundant computation: Naive recursion (like fibonacci) recalculates the same values. Use memoization or convert to iteration

PRACTICE PROBLEMS

Conditionals & Logic

Sorting & Comparators