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.
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
Try to recall each definition before you reveal it.
Quick check
Answer in your head first — then tap to check. No pressure.
Revision flashcards
Flip the card. Test yourself before the exam.
What is 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.
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.