Recursion Foundations

6 concept walkthroughs, each with a worked explanation and an interactive visualization, before you start solving problems in this area.

What is Recursion?

Recursion is when a function calls itself to solve a smaller version of the same problem. Instead of solving the whole thing at once, you break it into a tiny piece you CAN solve (the base case) and a smaller version of the original problem (the recursive case). The function keeps calling itself with smaller and smaller inputs until it hits the base case, then all the answers bubble back up. Let's see this in action with a classic example: computing factorial, given a number n, compute n! = n × (n-1) × ... × 1.

function factorial(n):
    if n <= 1:           // BASE CASE, stop here!
        return 1
    return n * factorial(n - 1)  // RECURSIVE CASE, smaller problem

The Call Stack

Every time a function calls another function (or itself), the computer saves a 'frame' on the call stack, like stacking plates. Each frame remembers the function's local variables, where it was in the code, and what it's waiting for. When the function returns, its frame is popped off the stack. In recursion, each recursive call adds a new frame. Too many calls without returning = Stack Overflow!

function sum_to(n):
    if n <= 0: return 0     // Base case: pop frame, return 0
    return n + sum_to(n-1)  // Push new frame, wait for result

// sum_to(4) builds this stack:
//   [sum_to(4)] waits for sum_to(3)
//   [sum_to(3)] waits for sum_to(2)
//   [sum_to(2)] waits for sum_to(1)
//   [sum_to(1)] waits for sum_to(0)
//   [sum_to(0)] returns 0  ← base case, start popping!
//   [sum_to(1)] returns 1+0 = 1
//   [sum_to(2)] returns 2+1 = 3
//   [sum_to(3)] returns 3+3 = 6
//   [sum_to(4)] returns 4+6 = 10

Base Case: The Safety Net

The base case is the condition where your recursive function STOPS calling itself and returns a value directly. Without it, recursion never ends: the function calls itself forever until the stack overflows. Every recursive function MUST have at least one base case. The base case answers: 'What's the simplest input I can solve immediately without any further recursion?'

// ❌ BAD: No base case, infinite recursion!
function broken(n):
    return broken(n - 1)   // Never stops!

// ✅ GOOD: Clear base case
function sum(n):
    if n == 0: return 0    // Base case: sum of nothing is 0
    return n + sum(n - 1)  // Recursive case

// ✅ Multiple base cases (Fibonacci)
function fib(n):
    if n == 0: return 0    // Base case 1
    if n == 1: return 1    // Base case 2
    return fib(n-1) + fib(n-2)

The Leap of Faith

The Leap of Faith is the #1 tip for writing recursive code. Here's the idea: ASSUME your recursive function already works correctly for smaller inputs. Don't trace through every call. Instead, focus on just THREE things: (1) What's the base case? (2) What does THIS one call need to do? (3) How do I combine my work with the result of the recursive call? If you get these three right, the recursion WILL work. Trust it.

// Sum of array using Leap of Faith
def sum_array(arr):
    if len(arr) == 0:        # Q1: simplest input → return 0
        return 0
    # Q2: TRUST sum_array(arr[1:]) gives correct sum of the rest
    return arr[0] + sum_array(arr[1:])
    # Q3: arr[1:] shrinks by 1 each time → guaranteed to reach []

Recursion vs Iteration

Every recursion can be converted to a loop (iteration), and vice versa. Recursion uses the call stack implicitly; iteration uses an explicit loop variable. Recursion is more natural for problems with a tree/branching structure (trees, graphs, backtracking). Iteration is simpler and more efficient for linear problems (summing an array, Fibonacci). Knowing WHEN to use each is a key skill.

// Factorial: both approaches

// RECURSIVE (implicit stack):
function factRec(n):
    if n <= 1: return 1
    return n * factRec(n - 1)

// ITERATIVE (explicit loop):
function factIter(n):
    result = 1
    for i = 2 to n:
        result = result * i
    return result

// Both compute the same thing!
// Iterative: O(1) space, no stack overhead
// Recursive: O(n) space from call stack

Common Recursion Patterns

Most recursive problems follow a few recurring patterns. Once you recognize which pattern a problem fits, writing the solution becomes formulaic. The main patterns are: (1) Counting down. Reduce n by 1 each call, (2) Building up return values. Accumulate results as calls return, (3) Passing state via parameters. Carry information DOWN the recursion, (4) Divide & conquer, split the problem in half. Learning these patterns gives you a toolkit for any recursive problem.

// Pattern 1: Reduce & Return (factorial)
function factorial(n):
    if n <= 1: return 1
    return n * factorial(n - 1)  // combine on way BACK

// Pattern 2: Accumulator (tail-recursive sum)
function sum(arr, i, acc=0):
    if i == arr.length: return acc
    return sum(arr, i+1, acc + arr[i])  // carry state DOWN

// Pattern 3: Divide & Conquer (merge sort)
function mergeSort(arr):
    if arr.length <= 1: return arr
    mid = arr.length / 2
    left = mergeSort(arr[0..mid])
    right = mergeSort(arr[mid..])
    return merge(left, right)

// Pattern 4: Build & Collect (subsets)
function subsets(nums, i, current, result):
    if i == nums.length:
        result.add(copy(current))
        return
    current.add(nums[i])        // include nums[i]
    subsets(nums, i+1, current, result)
    current.removeLast()        // exclude nums[i] (backtrack!)
    subsets(nums, i+1, current, result)

All DSA learning paths