First exams 2027 · HL only

B2.4.4 · Programming algorithms

Recursion

A function that calls itself sounds like it shouldn't work. It does, as long as every call gets a little bit closer to a point where it can stop and just answer directly.

HL only Typically 2–4 marks · AO2 Command term: explain, describe, identify

Explainer

Stand between two mirrors facing each other and you'll see your reflection, reflected again inside that reflection, and again inside that one, shrinking away into the distance. Each reflection is the exact same picture as the one before it, just one step smaller. Recursion works the same way in code: a function solves a problem by calling itself on a smaller version of that same problem, over and over, until the version left is small enough to answer without calling itself again.

Df

Recursion is a technique in which a function, procedure or algorithm calls itself, one or more times, breaking a problem down into a smaller instance of that exact same problem, until a condition is reached where it can stop calling itself and produce an answer directly.

Explainer

Every recursive function needs two parts, working together

Flynn is writing the countdown display for his school's science-fair rocket launch. It needs to print every number from whatever it's given down to zero, then announce liftoff.

def countdown(n):
    if n == 0:
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)

countdown(3) prints 3, then 2, then 1, then Liftoff!.

PartWhat it doesIn countdown(n)
Base caseThe termination condition, a solution that isn't recursive. This is the one input where the function stops calling itself and returns an answer directly.n == 0: prints "Liftoff!" and returns, no further call is made
General caseEvery other input. Does a small piece of the work, then calls the function again with an input that's moved one step closer to the base case.n > 0: prints n, then calls countdown(n - 1)
Consequence of a missing or unreachable base case

If a recursive function has no base case, or has one that a given input can never actually reach, every call makes another call and none of them ever return. In real Python this doesn't run forever: the interpreter has a call-stack limit, so after roughly a thousand nested calls it stops itself with RecursionError: maximum recursion depth exceeded. Deleting the if n == 0 lines from countdown above and calling countdown(3) would count down past zero, into the negatives, hundreds of times, until exactly that error appears.

Worked example

Winding down, then unwinding back up

Flynn also wants the total number of seconds the whole countdown display was on screen. He writes a second function, adding up every number from n down to 1:

def total_seconds(n):
    if n == 0:
        return 0
    return n + total_seconds(n - 1)

Notice the difference from countdown: this function's own work, the addition, happens after its recursive call returns, not before it. That single difference is what the stepper below is tracing.

Tracing total_seconds(3) Step 1 of 8

Winding, call 1. total_seconds(3) is called. n is 3, not the base case, so this call can't finish yet, it needs the answer to total_seconds(2) first.

total_seconds(3) → waiting on total_seconds(2)

Winding, call 2. total_seconds(2) is called. Also not the base case, it needs total_seconds(1) before it can finish.

total_seconds(3) → waiting on total_seconds(2) total_seconds(2) → waiting on total_seconds(1)

Winding, call 3. total_seconds(1) is called. Still not the base case, it needs total_seconds(0).

total_seconds(3) → waiting on total_seconds(2) total_seconds(2) → waiting on total_seconds(1) total_seconds(1) → waiting on total_seconds(0)

Base case reached. total_seconds(0) is called. n is 0, this is the base case: it returns 0 immediately, with no further call. Winding stops here, and unwinding begins.

total_seconds(3) → waiting on total_seconds(2) total_seconds(2) → waiting on total_seconds(1) total_seconds(1) → waiting on total_seconds(0) total_seconds(0) → base case, returns 0

Unwinding, 1st return. Now that total_seconds(0) has answered, total_seconds(1) can finish: it computes 1 + 0 and returns 1.

total_seconds(3) → waiting on total_seconds(2) total_seconds(2) → waiting on total_seconds(1) total_seconds(1) returns 1 (= 1 + 0)

Unwinding, 2nd return. total_seconds(2) now has its answer: it computes 2 + 1 and returns 3.

total_seconds(3) → waiting on total_seconds(2) total_seconds(2) returns 3 (= 2 + 1)

Unwinding, 3rd return. Finally total_seconds(3) has its answer: it computes 3 + 3 and returns 6.

total_seconds(3) returns 6 (= 3 + 3)

Result. total_seconds(3) evaluates to 6. Three calls were made while winding down, and none of them could finish until the base case answered. They then finished in exactly the reverse order they were made in: last in, first out, which is precisely how a stack behaves.

Winding order: total_seconds(3), total_seconds(2), total_seconds(1), total_seconds(0) Unwinding order: total_seconds(0), total_seconds(1), total_seconds(2), total_seconds(3) Final answer: 6

Try it yourself

Run both functions

Both functions from above, called on the same rocket-launch countdown. Try changing the starting number, or try adding a print statement inside total_seconds to watch the unwinding additions happen for yourself.

main.py
Loading Python engine…
Output
Press Run to see the output here.

Running in offline fallback mode. The full Python engine couldn't load (blocked school network, or no internet), so this console switched automatically to a small hand-written engine. It supports this page's functions and recursion, but it isn't full Python, and a genuinely infinite recursion here is stopped after 800 calls with a friendly error rather than crashing the page.

Explainer

Recursion vs iteration

total_seconds could just as easily have been written as a loop. Both reach the same answer; the real question is which one is the better fit for a given problem.

Recursion

Real example: traversing a binary search tree, where the same "check this node, then go left or right" logic naturally repeats at every level, however many levels the tree has.

Advantage

  • Often shorter and more elegant (a problem that's naturally defined in terms of a smaller version of itself, like a tree or a mathematical sequence, can be expressed with very little code)

Disadvantage

  • Heavy use of the stack (every waiting call sits in memory until it can unwind, which is memory-intensive and can overflow if too many calls stack up)
  • Can be slower (each call carries its own setup cost on top of the actual work, time that a loop doesn't spend)
  • Harder to follow and debug (the state at any moment is spread across many waiting calls instead of a few visible variables)
Iteration (a loop)

Real example: repeatedly asking the user to type a positive number until they enter one that's valid.

Advantage

  • Constant, predictable memory use (a loop reuses the same variables each pass, it doesn't add a new waiting call for every repetition)

Disadvantage

  • Can be clumsier for self-similar structures (a tree or nested structure often needs extra bookkeeping, like a manual stack, to loop over what recursion handles automatically)
!

Neither one is simply "better." A task like repeatedly validating one piece of input has no natural smaller sub-problem inside it, it's just the same simple check happening again, so a loop does it with less memory and less to go wrong. A task like searching a binary tree genuinely is the same smaller problem at every level, which is exactly where recursion earns its keep.

Explainer

Where recursion fits well

The syllabus names specific situations where recursion is the natural choice:

◉
  • Sorting algorithms that repeatedly split the data into smaller partitions and sort each partition the exact same way, then combine the results back together.
  • Traversing binary trees or graphs, where visiting a node means visiting its children, and each child is the root of its own smaller tree.
  • Fractal image creation, where a shape is drawn by drawing a smaller copy of the same shape, again and again, at a shrinking scale.
  • Mathematical problems defined recursively, such as factorials, the Fibonacci sequence, or the Towers of Hanoi puzzle, where the definition of the problem already describes itself in terms of a smaller version of itself.

Before reaching for recursion, it's worth checking: is there a genuine base case here? Does the problem actually split into a smaller version of itself, rather than just repeating the same fixed check? And would a loop reach the same answer just as clearly, with less memory overhead? If the honest answer to that last one is yes, a loop is usually the better choice.

Check your understanding

A recursive function is written with a general case, but its base case can never actually be reached for any input the function is called with. What happens when the function runs?

Common mistake

Markers reported this pattern when candidates were asked to define recursion

RecurringA common answer gives an incomplete definition: it names the "calling itself" part but leaves out the base case entirely, which loses marks even though the general idea is on the right track.

✕

Incomplete: "Recursion is when a function calls itself." True, but on its own this describes a function that would never stop calling itself. It's missing the one detail that makes recursion actually work.

✓

Complete: "Recursion is a technique where a function calls itself, on a smaller version of the same problem each time, until it reaches a base case where it can return an answer directly without calling itself again." Names both required parts: the self-call, and the base case that eventually stops it.

Revision questions

Past-paper style. Write an answer, then reveal the marking points and mark yourself.

Question 1 · 2 marks

[2]Define the term "recursion", making sure your answer explains what a base case is for.

Question 2 · 3 marks

[3]Explain what would happen if a recursive function's base case were removed, and identify one consequence of this for the program running it.

Question 3 · 4 marks

[4]A programmer wants to repeatedly ask the user to enter a positive number until valid input is given, and considers writing this using recursion. State two reasons why an iterative (loop-based) solution would be more appropriate here, referring to memory usage and code clarity in your answer.

Flashcards

Active recall for this statement’s key terms.