Programming technique · B2.4.4, B2.4.5 · Higher Level only
Recursion
Recursion occurs when a function or method calls itself on a smaller instance of the same problem. A reachable base case stops new calls; the pending calls then return in reverse order.
The three things every recursive design needs
Base case
A case that finishes without making another recursive call.
Recursive case
The case that performs the current step and makes exactly one smaller self-call in the simple non-branching model.
Progress
The recursive argument must move toward a reachable base case. Otherwise calls continue until the runtime fails.
A simple non-branching example
The precondition for this model is seconds >= 0. Every non-base call reduces seconds by one, so the base case at zero is eventually reached. The example deliberately uses a countdown rather than the summation problem in the challenge.
Trace both phases
| Phase | Call | What happens |
|---|---|---|
| Winding | showCountdown(3) | prints 3, then calls showCountdown(2) |
| Winding | showCountdown(2) | prints 2, then calls showCountdown(1) |
| Winding | showCountdown(1) | prints 1, then calls showCountdown(0) |
| Base | showCountdown(0) | prints Launch and returns without another call |
| Unwinding | return to showCountdown(1) | that call has no more work and returns |
| Unwinding | return to showCountdown(2) | that call returns |
| Unwinding | return to showCountdown(3) | the original call completes |
Check your understanding
Answer each question before opening the model answer.
-
What makes a base case different from a recursive case?
Reveal model answer
A base case finishes without making another recursive call. The recursive case makes the self-call.
-
Why is seconds - 1 important in the example?
Reveal model answer
It guarantees measurable progress toward the reachable base case seconds == 0 for the approved non-negative inputs.
-
What happens after showCountdown(0) returns?
Reveal model answer
The pending calls unwind in reverse order. In this example they have no further statements, so each simply returns to its caller.
-
Does recursion automatically use less memory than iteration?
Reveal model answer
No. Recursive calls require active call frames, so the simple depth-n model uses O(n) auxiliary call-stack space while a comparable loop may use O(1) auxiliary space.
Compare with an iterative solution
| Question | Recursive model | Iterative model |
|---|---|---|
| Time for this simple countdown | O(n) | O(n) |
| Auxiliary space | O(n) call depth | O(1) fixed variables |
| Possible advantage | Can match a recursively defined or self-similar problem directly | Often simpler for straightforward repetition |
| Possible limitation | Call overhead, depth-dependent memory and harder traces | May be less direct for naturally recursive structures |
Where recursion can be useful
Conceptual applications include fractal image generation, traversing binary trees and recursive sorting algorithms. The syllabus construction ceiling here is deliberately narrower: simple non-branching recursive algorithms only. You are not required to construct branching tree recursion or recursive quicksort on this page.
Challenges Choose one
Choose a challenge that feels appropriate for you. Code heat is only a rough estimate, not a fixed level.
Recursive Sum
SelectedConstruct a non-branching recursive sumTo method for non-negative integers. The base case returns 0 and the recursive case must make exactly one call on a smaller value. Hand-trace sumTo(4) through both the call phase and return phase, then test 0, 1 and several positive inputs.
Recursive Power
SelectedConstruct a recursive power(base, exponent) method for non-negative integer exponents. Use exponent == 0 as the base case and one recursive call on exponent - 1. Trace power(3, 4), explain how the argument moves toward the base case, and compare the recursive version with an iterative loop in terms of clarity and auxiliary memory.
Recursion Diagnosis
SelectedCreate three small non-branching recursive methods: one correct, one with a missing or unreachable base case, and one whose argument moves away from the base case. Predict what each will do before running it, then correct the two defective versions. Finish with a short explanation of one situation where recursion models the problem naturally and one limitation involving call overhead or depth-dependent memory use.
Selected challenge
This choice is shared with the portfolio setup page.
Plan your solution in handwritten pseudocode
Before opening your IDE or writing any program code, handwrite pseudocode for this challenge on paper.
Not marked complete. If you submit now, the GitHub README will record “No”.
Create your challenge folder
Run this command after planning. It creates the correct empty folder inside your portfolio.
Complete the challenge
Use your handwritten pseudocode as the starting plan, then write and test your solution in the folder created above.
Optional two-level scaffold
Try from your handwritten pseudocode first. Scaffold gives some structure; Scaffold + comments gives stronger guidance. Use only the level you need, and update your pseudocode first if the support changes your plan.
Submit for review
Run this when your program is complete. It creates the README, commits the folder and pushes it. The README records whether you marked the handwritten pseudocode as complete; the paper itself is handed to your teacher separately.