In simple terms
A friendly intro before the formal notes — no formulas yet.
The Russian Doll Problem
Recursion is a method where a function calls itself to solve smaller, identical versions of a problem until a simple, solvable 'base case' is reached. The call stack is a system memory structure that keeps track of all these calls, ensuring everything gets put back together correctly.
Imagine you have a set of Russian nesting dolls. To find the smallest doll, you open the current doll (the recursive step) to reveal a slightly smaller one inside. You repeat this process, opening doll after doll. Your 'base case' is when you open a doll and find it's solid, with no smaller doll inside. The call stack is like your memory of which dolls you've opened, so you can close them all back up in the reverse order once you've found the smallest one.
- 1
A recursive function is first called with the main problem's parameters. This initial call is placed (pushed) onto the call stack.
- 2
Inside the function, it calls itself with modified parameters that move it closer to a solution. This new call is pushed on top of the stack.
- 3
This process repeats. Each new recursive call adds another layer (a 'stack frame') to the top of the call stack.
- 4
When the 'base case' is finally met, the current function returns a value without making another recursive call. Its frame is removed (popped) from the stack, and control returns to the function below it, which can now complete its calculation and return its own value.
Explore the concept
Use the live diagram and synced steps — play it or tap a step card to walk through.
2 more simulations for this topic — run them in the Simulations section below
Simulations
Every simulation here runs the real model — try the steps on a card, then check what you see against the notes.
2 simulations
- GeoGebraCoreIB 5.1
Euclid's GCD as a chain of calls
Two sliders set a and b. The applet writes GCD(a, b) as a chain of smaller GCD calls, one per line, ending with a pair whose second number is 0.
Try this
- Set a = 63 and b = 46 and read down the lines: each one is GCD(b, a MOD b) of the line above.
- Find the last line. Its second number is 0, so this is the base case and the first number is the answer.
- Drag the sliders to find a pair that needs only two lines, then one that needs six or more.
Look for A recursive routine calls itself with smaller arguments until it meets the base case. The number of lines is how deep the call stack grows before it unwinds.
bowler · GeoGebra · GeoGebra Terms of Service
- GeoGebraIB 5.1
Tower of Hanoi
Three pegs and a pile of disks you move one at a time. A slider sets Number of Disks; counters show Moves and Minimum Required Moves.
Try this
- Solve it with 2 disks, then 3, keeping Moves equal to Minimum Required Moves.
- For 4 disks think recursively: move the top 3 to the spare peg, move the largest disk, then move the 3 back on top of it.
- Raise the Number of Disks slider one at a time and explain why each minimum is double the last plus one.
Look for Moving n disks is done by calling the same procedure twice for n − 1 disks, with a single disk as the base case. That is why the minimum is 2ⁿ − 1 moves.
Troy Nezki · GeoGebra · GeoGebra Terms of Service
Full topic notes
Formal explanation with the rigour you need for the exam.
The Anatomy of a Recursive Function
Every recursive algorithm has two essential components. The first is the base case, which is a simple condition that can be solved directly without further recursion. This is the stopping point. The second is the recursive step, where the function calls itself with a modified input that is a step closer to the base case. Without a correctly defined base case, a recursive function would call itself indefinitely, leading to a stack overflow error.
function recursiveFunction(parameters) if (base case is met) then return some simple value else // Modify parameters to move closer to base case return recursiveFunction(modified parameters) end if end function
The Call Stack: The Engine of Recursion
When a function is called in a program, the computer needs to keep track of where it was called from, so it can return to that point when the function finishes. The call stack is the data structure that manages this. It works on a Last-In, First-Out (LIFO) principle. Each time a function is called, a stack frame containing its local variables, parameters, and the return address is 'pushed' onto the top of the stack. When the function returns, its frame is 'popped' off the stack, and execution resumes at the stored return address.
The call stack is a system-level stack data structure.
It follows the LIFO (Last-In, First-Out) principle.
Each recursive call adds a new stack frame to the top of the stack.
When a base case is hit, the stack begins to 'unwind' as frames are popped off, and values are returned to the caller.
Recursion vs. Iteration
Most recursive algorithms can also be implemented iteratively using loops (like for or while). Recursive solutions are often more elegant and easier to read for problems that are naturally recursive, such as tree traversals or divide-and-conquer algorithms. However, they come at the cost of higher memory consumption due to the call stack overhead. Iterative solutions are generally more memory-efficient and can be faster due to the absence of function call overhead, but they can sometimes be more complex to write and understand.
In an exam, when asked to trace a recursive algorithm, always draw or describe the call stack. Explicitly show what is being pushed onto the stack with each call and what is being popped off as functions return. Mention the parameters for each call and the final return value. This structured approach ensures you don't miss any marks.
Worked examples
See the formulas applied — reveal one step at a time, like the exam.
A recursive function factorial(n) calculates . Trace the execution of factorial(4) showing the state of the call stack at each key step. The pseudocode is:
function factorial(n)
if n <= 1 then
return 1
else
return n * factorial(n - 1)
end if
end function
- 1
Call factorial(4): The main program calls factorial(4). A stack frame for factorial(4) is pushed onto the stack. Since , it must calculate 4 * factorial(3). It pauses and calls factorial(3).
A recursive binary search is performed on the sorted integer array to find the target value 19. The function signature is binarySearch(A, target, low, high). Trace the recursive calls, stating the values of low, high, and mid for each call.
- 1
Initial Call: binarySearch(A, 19, 0, 6)
How it all connects
The big idea sits in the middle — tap a linked idea to explore the link.
Tap a linked idea to see how it connects back to the main topic — that connection is what examiners reward.
Glossary
Key terms for this topic — skim now; the Check step will test them.
- base case
The first is the base case, which is a simple condition that can be solved directly without further recursion.
- call stack
The call stack is the data structure that manages this. It works on a Last-In, First-Out (LIFO) principle.
- Recursion
A programming technique where a function calls itself in order to solve a problem. The problem is broken down into smaller, similar sub-problems.
- Recursive step
The part of a recursive function where it calls itself, but with modified arguments that move it closer to the base case.
- Stack frame
A block of memory on the call stack that stores information for a single function call, including its parameters, local variables, and the return address.
- Stack overflow error
An error that occurs when the call stack runs out of memory. In recursion, this is typically caused by too many nested function calls, often due to a missing or incorrect base case.
- might iteration be
When memory is a concern, as iteration does not have the overhead of the call stack. Also for simpler problems where a loop is more readable and less prone to stack overflow errors.
- Tail recursion
A specific form of recursion where the recursive call is the very last action performed by the function. Modern compilers can optimize this to be as memory-efficient as an iterative loop.
Name it
Read the meaning, then pick which of this lesson’s terms it describes. Miss one and you see what your choice really means.
The part of a recursive function where it calls itself, but with modified arguments that move it closer to the base case.
Quick check
Write your answer first, then compare it with the model one — the gap is what you would have lost.
Teach it back
If you can explain it simply, you own it — gaps here are marks you’d lose.
Teach it back
Explain this topic as if teaching a friend. We name the gaps an examiner would still dock.
Revision flashcards
Guess first, then flip — retrieval beats re-reading.
Key takeaways
Review these before you close the topic — retrieval beats re-reading.
The call stack is a system-level stack data structure.
It follows the LIFO (Last-In, First-Out) principle.
Each recursive call adds a new stack frame to the top of the stack.
When a base case is hit, the stack begins to 'unwind' as frames are popped off, and values are returned to the caller.
Practice — then mark it
The whole point: a real Cambridge question, marked mark-by-mark.
Test Your Knowledge on Recursion and the Stack
Test Your Knowledge on Recursion and the Stack
Extra simulations & links
PhET, GeoGebra and other curated tools — open in a new tab.
Frequently asked
Checkpoint
One marked question is worth ten re-reads — close the loop before you move on.
Reading it isn’t knowing it — prove it.
Before you move on: do Test Your Knowledge on Recursion and the Stack on paper, snap a photo, and get examiner-style feedback on exactly where you win and lose marks.
Discuss Abstract data structures: recursion and the stack
Ask, share and discuss with other Computer Science HL students