In simple terms
A friendly intro before the formal notes — no formulas yet.
The Russian Doll of Code
Recursion is a programming technique where a function solves a problem by calling itself with a slightly smaller version of the same problem. This process repeats until it reaches a simple 'base case' that can be solved directly.
Imagine you have a set of Russian Matryoshka dolls. To find the smallest, solid doll, you open the largest doll to find a slightly smaller one inside. You repeat this process—opening the current doll to find the next—which is the recursive step. Eventually, you'll find a doll that doesn't open; this is the smallest one, your base case. You've now solved the problem and can put all the dolls back together.
- 1
Define the Base Case: Identify the simplest version of the problem that can be solved directly, without another function call. This is your exit condition.
- 2
Define the Recursive Step: Formulate how to solve a larger problem by breaking it down into a smaller, similar sub-problem and calling the same function on it.
- 3
Write the Function: Combine the base case and recursive step. Ensure the recursive call's arguments move it closer to the base case.
- 4
Trace the Execution: Follow the call stack as the function calls itself, reaches the base case, and then 'unwinds', returning values back up the chain of calls.
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 correctly written recursive function is composed of two fundamental parts. Without both, the function will either not work or, worse, crash your program.
Base Case: This is the condition that stops the recursion. It represents the simplest version of the problem that can be solved directly without making another recursive call. Every chain of recursive calls must eventually reach a base case.
Recursive Step: This is where the magic happens. The function calls itself, but with arguments that are modified to bring the problem closer to the base case. For example, if you're working with a number , the recursive call might be for n-1.
How Recursion Works: The Call Stack
To truly understand recursion, you must understand the call stack. The call stack is a region of memory that your program uses to keep track of active function calls. It operates on a Last-In, First-Out (LIFO) principle. When a function is called, a 'stack frame' containing its parameters, local variables, and a return address is pushed onto the stack. When the function finishes and returns, its frame is popped off the stack. In recursion, many frames for the same function are pushed onto the stack, each with different parameter values. If the recursion is too deep or infinite, the stack runs out of space, causing a 'stack overflow' error.
In Paper 4, you might be asked to trace a recursive function's execution and show the final return value. A good technique is to write down the chain of calls as shown in the factorial example, keeping track of the parameters at each step. Then, work your way back up the chain as the function returns, calculating the result at each level.
Recursion vs. Iteration
Every recursive algorithm can be rewritten using iteration (loops like FOR or WHILE), and vice versa. The choice between them is often a trade-off between performance and readability. Recursive solutions can be very elegant and closely mirror the mathematical definition of a problem, making the code easier to read and verify for certain tasks. However, they often come with a performance cost in terms of memory (call stack usage) and speed (function call overhead). Iterative solutions are typically more memory-efficient and faster but can sometimes be more complex to write, especially for problems with nested structures like trees.
Recursion Pros: Elegant, readable code for naturally recursive problems; can simplify complex logic.
Recursion Cons: Higher memory usage (risk of stack overflow); slower due to function call overhead; can be harder to debug.
Iteration Pros: More memory efficient (constant memory usage); faster execution; generally easier to trace for simple problems.
Iteration Cons: Can lead to more complex, less intuitive code for problems like tree traversal; managing state can be difficult.
Worked examples
See the formulas applied — reveal one step at a time, like the exam.
Write a recursive function in pseudocode, Factorial(n), that calculates the factorial of a non-negative integer . Trace the execution for Factorial(4).
- 1
Factorial(4) is called. Since 4 ≠ 0, it computes 4 * Factorial(3).
Write a recursive function Power(Base, Exponent) that calculates $Base^{Exponent}$, assuming the exponent is a non-negative integer. Trace the execution for Power(3, 4).
- 1
Power(3, 4) calls 3 * Power(3, 3)
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 method of solving a problem where the solution depends on solutions to smaller instances of the same problem. In programming, this is achieved when a function calls itself.
Key takeaways
Review these before you close the topic — retrieval beats re-reading.
- ✓
Base Case: This is the condition that stops the recursion. It represents the simplest version of the problem that can be solved directly without making another recursive call. Every chain of recursive calls must eventually reach a base case.
- ✓
Recursive Step: This is where the magic happens. The function calls itself, but with arguments that are modified to bring the problem closer to the base case. For example, if you're working with a number , the recursive call might be for n-1.
Practice — then mark it
The whole point: a real Cambridge question, marked mark-by-mark.
Test Your Recursion Skills
Test Your Recursion Skills
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 Recursion Skills on paper, snap a photo, and get examiner-style feedback on exactly where you win and lose marks.