How Recursion Works — Mental Model Cheat Sheet

This is a reference page, not a graded exercise. Recursion isn't an API you memorize — it's a shape you apply. Every recursive function needs exactly two pieces:

1. A base case — the smallest input(s) the function can answer directly, no further calls needed. This is what stops the recursion.
2. A recursive case — express the answer for the current input in terms of a call on a smaller subproblem, then combine that result with the current step's work.

The shape, in every language

// Java
int sumTo(int n) {
    if (n <= 0) return 0;          // base case
    return n + sumTo(n - 1);       // recursive case
}

// C#
int SumTo(int n) {
    if (n <= 0) return 0;
    return n + SumTo(n - 1);
}

# Python
def sum_to(n):
    if n <= 0:
        return 0
    return n + sum_to(n - 1)

// JavaScript / TypeScript
function sumTo(n: number): number {
  if (n <= 0) return 0;
  return n + sumTo(n - 1);
}

What's actually happening: the call stack

Each recursive call pushes a new stack frame — its own copy of the function's local variables and where it should resume once its own recursive call returns. sumTo(3) doesn't compute anything until sumTo(2) returns; sumTo(2) doesn't compute anything until sumTo(1) returns; and so on down to the base case. Then the calls resolve from the inside out:

sumTo(3)
= 3 + sumTo(2)
= 3 + (2 + sumTo(1))
= 3 + (2 + (1 + sumTo(0)))
= 3 + (2 + (1 + 0))
= 6

This is exactly why an unreachable or missing base case doesn't just give a wrong answer — it keeps pushing stack frames until the language throws a stack-overflow-style error (StackOverflowError in Java, RecursionError in Python, Maximum call stack size exceeded in JS).

Two shapes worth recognizing

Pattern	What it looks like	Example use
Linear recursion	one recursive call per invocation	factorial, sum of a list, reversing a linked list
Tree / branching recursion	two or more recursive calls per invocation	Fibonacci, subsets/permutations, binary tree traversals, divide-and-conquer (merge sort)

Branching recursion is where naive recursion can quietly become exponential (e.g. naive Fibonacci is O(2^n)) — if you notice a function calling itself more than once per invocation, it's worth asking out loud whether overlapping subproblems make memoization worth it.

The gotcha that costs the most time: forgetting to actually change the argument on the way down. sumTo(n) calling sumTo(n) again (instead of sumTo(n - 1)) compiles and runs — right up until it blows the stack. Before you write the recursive call, check that the argument is strictly moving toward the base case.