What is recursion in programming?

A loop that repeats a fixed number of times

A method of sorting numbers into order

A way of hiding code inside a class

Why is a base case essential in a recursive function?

It stops the recursion before the call stack overflows

It makes the function run faster

It tells the compiler which language to use

It declares the variables used inside the function

Which of the following are true about the call stack during recursion?

Each function call is added to the top of the stack

Calls are removed from the stack when they return a value

The stack unwinds as each call completes and passes its result back

The stack grows indefinitely even after the base case is reached

A function calculates factorial(4) recursively. Which sequence of calls is correct?

factorial(4) calls factorial(3), which calls factorial(2), which calls factorial(1); each returns its result back up the chain

factorial(4) → factorial(3) → factorial(2) → factorial(1) → returns 24

factorial(4) immediately returns 24 without any further calls

factorial(4) calls factorial(5) first, then works downward

Recursion

⏱ 7 min✏️ Quiz at the end

A Function That Calls Itself

Imagine standing between two mirrors facing each other. Each mirror reflects the other, and inside each reflection you can see another pair of mirrors reflecting again — seemingly forever. Recursion in programming has the same self-referential quality: a function that calls itself as part of its own definition.

What stops the reflections going on forever in real life? They fade. What stops a recursive function running forever? A base case — a condition that ends the chain of calls and starts returning results back up.

The Two Parts of Every Recursive Function

Every working recursive function has exactly two parts:

The base case — the simplest possible input, handled directly without another recursive call. This is the exit condition.
The recursive case — the general situation, which reduces the problem by one step and then calls the function again on that smaller version.

Without the base case, the function calls itself endlessly and the program crashes with a stack overflow error. Without the recursive case, the function never breaks down the problem and never does any real work.

Worked Example — Factorial

The factorial of a positive integer n (written n!) is the product of every integer from 1 up to n:

5! = 5 × 4 × 3 × 2 × 1 = 120

Notice the pattern: 5! = 5 × 4!. That is, the factorial of n is just n multiplied by the factorial of n − 1. This is a perfect fit for recursion.

FUNCTION factorial(n)
    IF n = 1 THEN          // base case
        RETURN 1
    ELSE                   // recursive case
        RETURN n * factorial(n - 1)
    ENDIF
ENDFUNCTION

Tracing factorial(4):

factorial(4)
  → 4 × factorial(3)
       → 3 × factorial(2)
            → 2 × factorial(1)
                 → 1          (base case reached)
            ← 2 × 1 = 2
       ← 3 × 2 = 6
  ← 4 × 6 = 24

Each call pauses, waiting for the next call to return, before it can complete its own multiplication.

The Call Stack

Every time a function is called, the computer adds a stack frame to the call stack — a record of where the program is and what its local variables hold. During recursion, the call stack grows one frame deeper with every recursive call. When the base case returns, the frames are unwound one by one back to the original call.

This is why recursion uses more memory than a simple loop: ten recursive calls mean ten stack frames sitting in memory at once. A very deep recursion (thousands of calls) can exhaust available stack space, producing a stack overflow.

Worked Example — Countdown

A simpler recursive example counts down from any number to zero:

FUNCTION countdown(n)
    IF n = 0 THEN
        OUTPUT "Go!"
        RETURN
    ENDIF
    OUTPUT n
    countdown(n - 1)
ENDFUNCTION

Calling countdown(3) prints:

3
2
1
Go!

Each call outputs its own number, then hands off to the next. When n reaches 0, the base case fires and no further calls are made.

Recursion vs Iteration

Any problem solvable with recursion can also be solved with a loop (iteration), and vice versa. So why use recursion at all?

Some problems have a naturally recursive structure — their solution is defined in terms of a smaller version of itself. The most famous examples include tree traversal, directory searching, and certain sorting algorithms like merge sort. Writing these iteratively requires manually managing a stack in your own code, which is often more complex than simply letting the function call itself.

Recursion is cleaner for problems like these. Iteration is often more efficient for problems that are just repetitive, such as summing a list.

Common Pitfalls

Forgetting the base case is the most frequent mistake. Always ask: "What is the simplest input this function could receive, and can I handle it directly without another call?"

Not moving toward the base case is the other trap. Each recursive call must make progress — the input must get smaller (or simpler) with every call. If n never decreases, the function loops forever.

Key Words

Recursion — a technique where a function calls itself as part of its definition
Base case — the simplest input that is handled directly, stopping further calls
Recursive case — the general situation, which reduces the problem and calls the function again
Call stack — the memory structure that tracks all active function calls
Stack frame — a single entry on the call stack, recording one function call's local state
Stack overflow — the crash that occurs when recursion goes too deep and exhausts available stack memory
Unwinding — the process of returning results back up through the chain of calls after the base case is reached