Recursion — Functions That Call Themselves
How a function can solve a problem by solving a smaller version of itself
This concept builds on Boolean Logic — The Language of Computers. Consider exploring it first for the best experience.
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
-
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
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
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
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
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
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
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.
Connected Concepts
Sorting
Merge sort uses recursion to divide and conquer.
Binary Numbers
Converting to binary is a natural recursive process.
Fibonacci Sequence
F(n) = F(n−1) + F(n−2) is a classic recursive definition — watch it build term by term.
Stacks & Queues
The call stack is a real stack: the last call made is the first one to return.
Dynamic Programming
Memoization turns the exploding Fibonacci tree into a short chain — the core idea of dynamic programming.
Big O Notation
One call per level grows linearly; two calls per level grow exponentially. Big O names the difference.
Tower of Hanoi
Moving n disks means moving n − 1 disks twice around one move of the largest, so the recursion takes 2ⁿ − 1 moves.
Updated
- — New connection to Tower of Hanoi.
- — New Fibonacci call tree with a memoize toggle, a worked factorial example, and more quiz questions.