Recursion

Why recursion exists (motivation before mechanics)

Some problems are naturally self-similar: the overall structure repeats inside smaller parts.

• •A folder contains subfolders, which contain subfolders.
• •A tree has subtrees, each of which is a tree.
• •A sorted array can be searched by looking at half, then half of half, etc.
• •Many mathematical definitions are recursive: factorial, Fibonacci, linked lists.

Recursion is a technique for expressing that self-similarity directly in code: a function calls itself to solve a smaller version of the same problem.

Definition

A function is recursive if it (directly or indirectly) invokes itself.

A well-formed recursive function has two essential parts:

1) Base case: a condition where the function returns an answer without making another recursive call.

2) Recursive case: a rule that reduces the problem to one or more smaller instances of itself.

The “progress measure” idea (the secret to termination)

To prevent infinite recursion, each recursive call must make progress toward the base case.

Think of a quantity that always decreases and can’t decrease forever. Common measures:

• •n decreases: n → n − 1 until n = 0
• •interval size decreases: hi − lo shrinks each call
• •list length decreases: len(xs) goes down
• •tree height decreases: move to a child node

Mathematically, you want a well-founded measure: there is no infinite strictly-decreasing sequence. The natural numbers ℕ with “>” are well-founded, because you can’t keep subtracting 1 forever without hitting 0.

A tiny example: factorial

Factorial is often defined recursively:

• •0! = 1 (base case)
• •n! = n · (n − 1)! for n ≥ 1 (recursive case)

In code-like pseudocode:

fact(n):
  if n == 0: return 1
  else: return n * fact(n-1)

Here:

• •Base case: n == 0
• •Progress measure: n decreases by 1 each call

Recursion and the call stack (link to what you already know)

You already know stacks (LIFO). Recursion uses the call stack automatically.

When fact(4) calls fact(3), the program needs to remember:

• •what n was (4)
• •that it should multiply the returned result by 4

That “remembering” is stored in a stack frame on the call stack. Then fact(3) calls fact(2), pushing another frame, and so on.

When the base case returns, results flow back upward, popping frames as each call completes.

Recursion vs. iteration (not rivals, just different expressions)

Many recursive functions can be rewritten as loops. Recursion is often clearer when:

• •the structure is hierarchical (trees, nested objects)
• •divide-and-conquer naturally splits the input
• •you want a direct translation of a recursive definition

But recursion can use more stack space and can overflow if too deep. You’ll learn to choose based on clarity and constraints.

Why this mechanic matters

People new to recursion often focus on “the function calls itself” and forget that recursion is really about two responsibilities:

• •Stopping (base case)
• •Reducing (recursive case)

If either part is wrong, you get infinite recursion, wrong answers, or runtime errors.

A mental model that actually works

When reasoning about recursion, use this disciplined viewpoint:

1) Assume the recursive call works on smaller inputs.

2) Use it to build the solution for the current input.

3) Verify that you eventually reach the base case.

This is basically informal induction.

Example: sum of first n natural numbers

Define S(n) = 1 + 2 + … + n.

Recursive definition:

• •S(0) = 0
• •S(n) = n + S(n − 1)

Pseudocode:

sumTo(n):
  if n == 0: return 0
  else: return n + sumTo(n-1)

Stack trace intuition (small input)

Call sumTo(3):

• •sumTo(3) needs 3 + sumTo(2)
• •sumTo(2) needs 2 + sumTo(1)
• •sumTo(1) needs 1 + sumTo(0)
• •sumTo(0) returns 0

Now unwind:

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

Notice the call stack is LIFO:

• •Calls push frames: 3,2,1,0
• •Returns pop frames: 0,1,2,3

Two common base-case styles

Base cases depend on the problem. Two patterns show up often:

1) Minimal input base case

• •n == 0
• •empty list []
• •null node / leaf

2) Small threshold base case

• •for merge sort: when len(arr) ≤ 1
• •for binary search: when lo > hi

The key is that the base case is guaranteed to occur if the recursive case keeps making progress.

A table of common recursive shapes

At difficulty 2, linear recursion is the easiest place to get fluent, but you should recognize the others so recursion doesn’t feel mysterious later.

Spotting “hidden” recursion: indirect self-calls

A calls B calls A:

A(x):
  ... return B(x-1)
B(x):
  ... return A(x-1)

This is still recursion (mutual recursion). It still needs:

• •base case somewhere
• •progress measure across the cycle

Practical caution: recursion depth

Each recursive call adds a stack frame. If the recursion is too deep, you can hit a stack overflow.

For linear recursion on large n, a loop is often safer. Later, you’ll learn techniques like tail recursion (and language-specific optimizations), but the first step is simply being aware that recursion consumes stack space proportional to depth.

Why “progress” deserves its own section

Many recursion bugs have a base case, but still never reach it because the recursive step doesn’t move closer.

Example of a broken recursive case:

countDown(n):
  if n == 0: return
  else: countDown(n)   # progress measure does not decrease

It has a base case (n == 0) but never reaches it.

So we need a way to prove we’re moving toward termination.

Progress measures: the idea

A progress measure is a value m(input) ∈ ℕ (often) such that:

• •m(input) ≥ 0 for all valid inputs
• •each recursive call strictly decreases the measure

Formally, if f calls f on inputs x → x′, we want:

m(x′) < m(x)

Since ℕ has no infinite strictly decreasing sequences, recursion must eventually stop.

Examples of measures

1) Integer countdown

• •Input: n
• •Measure: m(n) = n
• •Decrease rule: call on n − 1

2) List processing

• •Input: list xs
• •Measure: m(xs) = len(xs)
• •Decrease rule: call on tail(xs) (length decreases by 1)

3) Range shrinking

• •Input: (lo, hi)
• •Measure: m(lo, hi) = max(0, hi − lo + 1)
• •Decrease rule: choose a smaller subrange

Connecting progress to correctness (informal induction)

Recursion correctness typically follows the same structure:

1) Base case correctness: show the function returns the right answer on the base case.

2) Inductive step: assume the function works for all smaller measures; prove it works for the current input.

You don’t need formal proofs for every function, but this mindset prevents “wishful recursion.”

Worked-through reasoning example: list sum

Suppose we define a function sum(xs).

Recursive idea:

• •Base case: empty list sums to 0
• •Recursive case: sum of list is head + sum(tail)

Let xs = [x₀, x₁, …, xₖ].

• •Base: sum([]) = 0
• •Step: sum([x₀] + rest) = x₀ + sum(rest)

Progress measure: m(xs) = len(xs). Each call uses rest where len(rest) = len(xs) − 1.

Correctness intuition:

• •If we already know sum(rest) is correct (smaller list), then adding x₀ produces the correct total.

Another subtle progress issue: off-by-one in the wrong direction

Broken variant:

fact(n):
  if n == 0: return 1
  else: return n * fact(n+1)

This moves away from the base case: n grows, and you never hit 0.

The progress measure test catches this immediately:

• •m(n) = n does not decrease; it increases.

When measures aren’t simple numbers

Sometimes the input is a structure (like a tree). You can still measure progress:

• •height of the remaining subtree
• •number of nodes remaining to visit

Even if you never compute the measure explicitly, you should be able to point to it in your reasoning.

Summary checklist (use this when writing recursion)

Before you run your code, answer:

1) What is the base case?

2) What input(s) does the recursive call use?

3) What is the progress measure?

4) Does the measure strictly decrease on every path?

5) Does the recursive case combine results correctly?

If you can answer these, the recursion is usually correct and terminating.

Why recursion becomes a “core tool” in algorithms

Recursion is not just a coding trick; it’s a way to express algorithmic structure.

Many major algorithm families are easiest to understand recursively first, and then (sometimes) optimized into iterative forms.

1) Divide and Conquer

Divide-and-conquer means:

1) Split the problem into smaller subproblems

2) Solve each subproblem (often recursively)

3) Combine the results

Example: merge sort

• •Split array into two halves
• •Recursively sort each half
• •Merge the two sorted halves

Progress measure: n = array length; each call handles roughly n/2.

This is the gateway to analyzing runtime with recurrence relations like:

T(n) = 2T(n/2) + O(n)

You’re not solving recurrences yet in this node, but recursion is what creates them.

2) Dynamic Programming (memoization starts as recursion)

Many problems have:

• •optimal substructure: the best solution uses best solutions to subproblems
• •overlapping subproblems: the same subproblem appears many times

A common path:

1) write a clean recursive solution

2) notice repeated calls

3) add memoization (cache) → dynamic programming

Classic example: Fibonacci.

Naive recursion:

• •F(0)=0, F(1)=1
• •F(n)=F(n−1)+F(n−2)

This is correct but repeats work. Memoization keeps the recursive clarity while improving performance.

3) Tree/graph traversals

Depth-first search (DFS) on a tree is naturally recursive:

• •Visit a node
• •Recursively visit each child

Progress measure: remaining nodes / subtree height.

(For general graphs, you must also track visited nodes to avoid cycles—otherwise recursion may not terminate even if depth decreases in some branches.)

4) Parsing and nested data

Anything nested—parentheses, JSON-like structures, expression trees—often becomes simpler with recursion.

Recursion and stacks: the conceptual bridge

Since you already know stacks, here’s the key connection:

• •Recursion is “using the call stack as an implicit stack.”
• •Rewriting recursion iteratively often means “use your own explicit stack.”

This is a powerful translation:

Understanding this makes recursion feel less like magic and more like a design choice.

When not to use recursion

Recursion is great when it matches the problem structure. But you should consider alternatives when:

• •depth can be huge (risk of stack overflow)
• •an iterative solution is much clearer
• •performance requires tight control

Even then, learning recursion first is often the best route to a correct solution.