Recursion — Functions That Call Themselves

How a function can solve a problem by solving a smaller version of itself

Computer Science Algorithms intermediate 9 min

This concept builds on Boolean Logic — The Language of Computers. Consider exploring it first for the best experience.

Step 1 of 7

A Function Calls Itself

A recursive function solves a problem by calling itself with a smaller input. Watch the stack of boxes grow downward: factorial(5) asks factorial(4), which asks factorial(3), and so on. Each box is a call that is still waiting for an answer. Move the "Depth" slider to choose a different starting number.

The Base Case

Without a stopping condition, recursion never ends. The base case is the simplest input that can be solved directly — here factorial(1) = 1. Look for the green BASE CASE box at the bottom of the stack: it is the first call that returns a value instead of making another call.

The Call Stack Unwinds

Each call sits on the call stack until the call below it returns. Once the base case answers, the gold values travel back up one box at a time: each frame multiplies its own number by the answer it just received, then hands the result to the frame above.

Worked Example: factorial(5) = 120

Going down, five calls wait: 5 × factorial(4), 4 × factorial(3), 3 × factorial(2), 2 × factorial(1), and the base case factorial(1) = 1. Coming back up: 2 × 1 = 2, 3 × 2 = 6, 4 × 6 = 24, and finally 5 × 24 = 120. The stack was 5 frames deep — one per number.

What If There Is No Base Case?

Tick "What if there's no base case?" and watch the stack sail past 1 into factorial(0), factorial(-1) and beyond. Nothing ever returns, so frames pile up until the program runs out of stack space and crashes with a stack overflow — the error every recursive function risks without a stopping rule.

Branching Recursion: Fibonacci

Choose "Fibonacci — two calls each" in the "Function" menu. Now every call that is not a base case makes two calls: fib(k) = fib(k−1) + fib(k−2). The stack becomes a tree. Red circles redo work already finished elsewhere in the tree, and the counter shows that 9 of fib(5)'s 15 calls repeat an earlier call.

Memoization: Remember Answers

Tick "Remember answers (memoize)". Each answer is stored the first time it is worked out, so a repeated call reads the stored value instead of recursing again — those appear as dashed blue circles. fib(5) drops from 15 calls to 9, and fib(6) from 25 to 11.

How It Works — Step by Step

Step 1 of 7
  1. 1

    A Function Calls Itself

    A recursive function solves a problem by calling itself with a smaller input. Watch the stack of boxes grow downward: factorial(5) asks factorial(4), which asks factorial(3), and so on. Each box is a call that is still waiting for an answer. Move the "Depth" slider to choose a different starting number.

  2. 2

    The Base Case

    Without a stopping condition, recursion never ends. The base case is the simplest input that can be solved directly — here factorial(1) = 1. Look for the green BASE CASE box at the bottom of the stack: it is the first call that returns a value instead of making another call.

  3. 3

    The Call Stack Unwinds

    Each call sits on the call stack until the call below it returns. Once the base case answers, the gold values travel back up one box at a time: each frame multiplies its own number by the answer it just received, then hands the result to the frame above.

  4. 4

    Worked Example: factorial(5) = 120

    Going down, five calls wait: 5 × factorial(4), 4 × factorial(3), 3 × factorial(2), 2 × factorial(1), and the base case factorial(1) = 1. Coming back up: 2 × 1 = 2, 3 × 2 = 6, 4 × 6 = 24, and finally 5 × 24 = 120. The stack was 5 frames deep — one per number.

  5. 5

    What If There Is No Base Case?

    Tick "What if there's no base case?" and watch the stack sail past 1 into factorial(0), factorial(-1) and beyond. Nothing ever returns, so frames pile up until the program runs out of stack space and crashes with a stack overflow — the error every recursive function risks without a stopping rule.

  6. 6

    Branching Recursion: Fibonacci

    Choose "Fibonacci — two calls each" in the "Function" menu. Now every call that is not a base case makes two calls: fib(k) = fib(k−1) + fib(k−2). The stack becomes a tree. Red circles redo work already finished elsewhere in the tree, and the counter shows that 9 of fib(5)'s 15 calls repeat an earlier call.

  7. 7

    Memoization: Remember Answers

    Tick "Remember answers (memoize)". Each answer is stored the first time it is worked out, so a repeated call reads the stored value instead of recursing again — those appear as dashed blue circles. fib(5) drops from 15 calls to 9, and fib(6) from 25 to 11.

Key Takeaways

Base case is essential

Every recursive function must have a base case that stops the recursion. Without it, you get a stack overflow.

Trust the recursion

You don't need to trace every level. Trust that factorial(n-1) returns the right answer and just write factorial(n) = n × factorial(n-1).

Stack depth = input size

For factorial(10), the stack grows 10 levels deep. Very large inputs can overflow the call stack — this is the "stack overflow" in the error name.

Branching multiplies work

When each call makes two calls, the number of calls roughly doubles with every step of n. Memoization stores each answer once, so the work grows in a straight line instead.

Added
Updated
  • — New connection to Tower of Hanoi.
  • — New Fibonacci call tree with a memoize toggle, a worked factorial example, and more quiz questions.