Learn
B2.4.5 | RECURSIVE ALGORITHMS (HL ONLY)
01 | TURN THE RECURSIVE IDEA INTO A PROGRAM
In the previous lesson, recursion meant solving a smaller version of the same problem. Now we will construct complete functions and trace precisely when instructions execute, when calls pause and what each call returns.
This HL-only objective focuses on simple, non-branching recursive algorithms in a programming language. Each execution of a recursive case makes at most one recursive call, creating a single chain rather than a tree of recursive calls.
An if statement choosing between a base case and a recursive case is still allowed. “Non-branching” here describes the recursive call pattern, not a ban on selection statements.
02 | START WITH A CONTRACT AND A SMALL EXAMPLE
Suppose sum_to(n) must return the sum of integers from 1 to n, for a non-negative integer n. sum_to(4) should return 10; sum_to(1) should return 1; sum_to(0) should return 0.
The empty sum at n = 0 supplies a base case. For positive n, the remaining sum is the same problem at n − 1, so sum_to(n) = n + sum_to(n − 1).
Write these expected results before the code. They tell us both what the base case should return and how the smaller result contributes to the answer.
03 | CONSTRUCT A SUM FUNCTION
def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)
print(sum_to(4))
The result is 10. The function assumes n is a non-negative integer. The comparison n == 0 selects the base case; otherwise the return expression adds n to the answer from the smaller call.
The smaller call must finish before addition can complete. At n = 4, the pending operation is 4 + the result of sum_to(3), not 4 + 3.
The function returns a value; the outer print displays that returned value once. The function itself does not print every intermediate sum.
04 | TRACE THE CALLS BEFORE THE RETURNS
| Call entered | Local n | Expression waiting to finish |
|---|---|---|
| sum_to(4) | 4 | 4 + sum_to(3) |
| sum_to(3) | 3 | 3 + sum_to(2) |
| sum_to(2) | 2 | 2 + sum_to(1) |
| sum_to(1) | 1 | 1 + sum_to(0) |
| sum_to(0) | 0 | Base case: return 0 |
Each row is a different active invocation. Local n does not keep changing in the same frame; each new call receives its own parameter value.
There are five calls in this chain, including the base-case call. Only four of those calls make another recursive call. State what is being counted when asked for a call count.
05 | COMPLETE THE RETURN TRACE
| Call finishing | Smaller result | Pending operation completed | Returned value |
|---|---|---|---|
| sum_to(0) | Not needed | Base case | 0 |
| sum_to(1) | 0 | 1 + 0 | 1 |
| sum_to(2) | 1 | 2 + 1 | 3 |
| sum_to(3) | 3 | 3 + 3 | 6 |
| sum_to(4) | 6 | 4 + 6 | 10 |
The returned value from one row becomes the smaller result used by the next waiting call. This is unwinding: each call finishes its work and hands its result to its caller.
Do not write 4, 3, 2, 1, 0 as the sum results. Those are the arguments on descent. The returned sums are 0, 1, 3, 6 and 10 on ascent.
06 | INTERACTIVE: CHANGE THE PROGRAM, FOLLOW THE CHAIN
Select one of four supplied non-branching programs and a whole-number n from 0 to 6. The model separates call entry, printed output and return actions. Frames are shown newest first; the history records their state after each action.
First predict the complete output and returned result. Then step through to see whether printing happens while the stack grows or while it shrinks. The activity models only the supplied programs and does not execute arbitrary code.
07 | CHOOSE THE RIGHT BASE RESULT
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
The output is 24. Factorial uses multiplication, so its base result is 1: multiplying by 1 preserves the accumulated product. The sum example uses 0 because adding 0 preserves the sum.
Changing factorial’s base result to 0 makes every positive result 0. The calls would still terminate for the permitted inputs, but the answers would be wrong.
A base result comes from the required mathematical or logical meaning, not from a rule that every recursive function should return the same value at its stopping case.
08 | PRINT BEFORE: OUTPUT ON DESCENT
def countdown(n):
if n == 0:
return
print(n)
countdown(n - 1)
countdown(4)
The output is 4, 3, 2, 1 on separate lines. Each positive call prints its own n before starting the smaller call. The base case returns without printing 0.
After the base case, the waiting calls finish without another print. These functions return None; the printed sequence is their side effect, not a numerical returned result.
A bare return ends the current Python call and supplies None. It does not instantly end every waiting call or exit the whole program.
09 | PRINT AFTER: OUTPUT ON UNWINDING
def count_up(n):
if n == 0:
return
count_up(n - 1)
print(n)
count_up(4)
The output is 1, 2, 3, 4. No positive call can reach its print until its smaller call has finished. The deepest positive call prints 1 first, then its caller prints 2, and so on.
Moving one instruction from before the recursive call to after it reverses this output order. The argument sequence is still 4, 3, 2, 1, 0 in both programs.
The call order and output order need not be the same. A strong trace distinguishes them explicitly.
10 | PUT BOTH SIDES OF THE CALL IN ONE TRACE
def visit(n):
if n == 0:
return
print("Enter", n)
visit(n - 1)
print("Leave", n)
visit(2)
The exact output is Enter 2, Enter 1, Leave 1, Leave 2, each on its own line. The n = 0 call prints nothing.
There is only one recursive call in each positive invocation. Two print statements do not make the recursion branching.
When a call returns, resume at the statement after the call site in its caller. Do not restart the caller’s body from its first print.
11 | USE A LOCAL VARIABLE FOR THE SMALLER RESULT
def sum_to(n):
if n == 0:
return 0
smaller = sum_to(n - 1)
answer = n + smaller
return answer
print(sum_to(3))
This returns 6 and has the same result as return n + sum_to(n − 1). Naming smaller can make the waiting calculation easier to trace.
The assignment to smaller is not complete until the recursive call returns. For the outer n = 3 call, smaller eventually receives 3, then answer becomes 6.
Each call has a separate smaller and answer when execution reaches those assignments. Do not fill them with values before they exist.
12 | BUILD A RELIABLE TRACE TABLE
| Stage | Call / local n | smaller | answer | Action |
|---|---|---|---|---|
| Descent | sum_to(3) / 3 | Not assigned | Not assigned | Call sum_to(2) |
| Descent | sum_to(2) / 2 | Not assigned | Not assigned | Call sum_to(1) |
| Descent | sum_to(1) / 1 | Not assigned | Not assigned | Call sum_to(0) |
| Base | sum_to(0) / 0 | Not assigned | Not assigned | Return 0 |
| Return | sum_to(1) / 1 | 0 | 1 | Return 1 |
| Return | sum_to(2) / 2 | 1 | 3 | Return 3 |
| Return | sum_to(3) / 3 | 3 | 6 | Return 6 |
Label unassigned values honestly rather than inventing zeroes. A value of 0 and a name that has not yet been assigned are different states.
Follow the code’s actual statements and requested trace format. A compact return-expression version may not have local variables named smaller or answer at all.
13 | CONSTRUCT A POWER FUNCTION
def power(base, exponent):
if exponent == 0:
return 1
return base * power(base, exponent - 1)
print(power(3, 4))
The result is 81. The domain here is numeric base and non-negative integer exponent. The base case uses exponent = 0; each recursive call reduces the exponent but keeps base unchanged.
For this teaching convention, power(base, 0) returns 1, including power(0, 0). If an application needs a different policy for that input, specify and implement it.
Trace power(3, 2): the calls use exponents 2, 1, 0; the returns are 1, 3, 9. The changing problem size is the exponent, not the base.
14 | A DIFFERENT REDUCTION: SUM OF DIGITS
def digit_sum(n):
if n < 10:
return n
return n % 10 + digit_sum(n // 10)
print(digit_sum(472))
The result is 13. For a non-negative integer n, n % 10 gives its final digit, while n // 10 removes that digit. Thus digit_sum(472) = 2 + digit_sum(47), then 7 + digit_sum(4).
The base case is any single digit, including 0. Its digit sum is simply itself. The calls reduce the number of digits rather than subtracting 1 each time.
The return chain is 4, then 7 + 4 = 11, then 2 + 11 = 13. This still makes at most one recursive call per invocation.
15 | PROCESS A LIST USING AN INDEX
def sum_from(values, index):
if index == len(values):
return 0
return values[index] + sum_from(values, index + 1)
values = [8, 5, 7]
print(sum_from(values, 0))
The result is 20. Valid starting indexes here are integers from 0 through len(values), inclusive. At len(values), there are no items left to add, so the base case returns 0 before any indexing occurs.
The index increases, but the remaining item count decreases. Progress toward a base case does not always mean the argument itself must become smaller.
Passing the same list and a new index avoids making a fresh slice of the remaining list at each call. It also makes the current position explicit for a trace.
16 | CONSTRUCT FROM A SCENARIO: COUNT TARGET VALUES
def count_from(values, target, index):
if index == len(values):
return 0
contribution = 0
if values[index] == target:
contribution = 1
return contribution + count_from(values, target, index + 1)
print(count_from([7, 4, 7, 9], 7, 0))
The output is 2. Each item contributes 1 for a match or 0 for a nonmatch. The contribution is added to the count from the remaining suffix. The starting-index contract is the same as for sum_from.
This uses selection to decide contribution, but still calls itself only once per non-base invocation. It remains non-branching recursion.
Start with the smallest subproblem: an empty remaining suffix contains zero matches. Then define how the current item changes that smaller answer.
17 | DESIGN THE DOMAIN AND GUARD THE ENTRY
def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)
def checked_sum_to(n):
if type(n) is not int or n < 0:
raise ValueError("Use a non-negative integer")
return sum_to(n)
print(checked_sum_to(4))
The wrapper validates the entry once, then delegates to the recursive helper whose contract assumes valid input. type(n) is int deliberately excludes Boolean values in this example.
Validation of the domain does not guarantee that every huge valid n will fit the runtime’s stack resources. This is an educational recursive sum, not a claim that it is the best implementation for arbitrarily large inputs.
If the task already guarantees valid inputs, state that precondition instead of burying the essential algorithm under repeated input handling.
18 | CORRECT ERRORS BY CHECKING THE CONTRACT
| Faulty idea | Effect | Repair |
|---|---|---|
| sum_to calls sum_to(n) | No progress | Call with n − 1 for this domain |
| sum_to base returns 1 | All sums too large by 1 | Return the empty sum 0 |
| Call smaller function but omit return | Caller can receive None | Return the promised combined result |
| Print placed on wrong side of call | Wrong output sequence | Match placement to required order |
| sum_from accesses values[index] before base check | Out-of-range access at end | Test exhaustion before indexing |
For each repair, explain why it fixes the requirement. Testing one input can show a defect, but the base case and reduction should justify the behaviour across the permitted domain.
19 | REPAIR THE MISSING RETURN
def sum_to(n):
if n == 0:
return 0
smaller = sum_to(n - 1)
return n + smaller
print(sum_to(2))
The result is 3. If the final line were only n + smaller, Python would evaluate and discard the expression, then implicitly return None. A waiting caller trying to add that None could fail with TypeError.
Printing n + smaller is also not a substitute for returning it. The result must travel back to the waiting expression, not merely appear on the screen.
20 | TEST BASE, NEAR-BASE AND ORDINARY CASES
| Algorithm | Tests | Expected results |
|---|---|---|
| sum_to | 0, 1, 4 | 0, 1, 10 |
| factorial | 0, 1, 4 | 1, 1, 24 |
| power | (3,0), (3,1), (3,4) | 1, 3, 81 |
| digit_sum | 0, 7, 472 | 0, 7, 13 |
| sum_from starting at 0 | [], [5], [8,5,7] | 0, 5, 20 |
| count_from starting at 0 | Empty, no matches, duplicates | 0, 0, correct repeated-match count |
The base case checks the direct answer. A near-base case checks one recursive step and combination. A larger ordinary input checks multiple retained calls and returns.
For output-producing functions, test the exact order and number of printed lines as well as the returned None. For invalid inputs, test the documented wrapper policy separately.
21 | WORK AND DEPTH DEPEND ON THE REDUCTION
For sum_to(n) and factorial(n), there are n + 1 calls including the base call. Under the unit-cost arithmetic model, time and maximum active-call space are O(n).
For sum_from at starting index 0, n items also produce n + 1 calls. For power(base, exponent), time and depth are O(exponent) in this straightforward repeated-multiplication version.
For digit_sum, each call removes one digit, giving O(d) calls for d digits. For positive numeric value n, d grows as O(log n). Distinguish the numeric magnitude from the number of digits used to represent it.
Large-integer arithmetic has costs beyond this simplified unit-cost model. The purpose here is to connect the recursive reduction with the execution count and retained frames.
22 | A SINGLE CHAIN DOES NOT MEAN CONSTANT SPACE
Non-branching recursion creates only one next recursive call per invocation, but earlier invocations can remain active. A chain of n levels can therefore retain O(n) frames.
The displayed factorial and sum return expressions have pending multiplication or addition, so they are not tail-recursive. Even a tail-recursive rewrite does not automatically remove frames in ordinary Python execution.
A loop can often perform these simple linear tasks with a fixed number of auxiliary variables under the same simplified model. Choose recursion for clarity or the task requirement while recognizing the space trade-off.
23 | JAVA: SUM AND OUTPUT TIMING
public class RecursiveTraceExample {
static int sumTo(int n) {
if (n == 0) {
return 0;
}
return n + sumTo(n - 1);
}
static void countUp(int n) {
if (n == 0) {
return;
}
countUp(n - 1);
System.out.println(n);
}
public static void main(String[] args) {
System.out.println(sumTo(4));
countUp(3);
}
}
The output lines are 10, 1, 2, 3. The methods assume small non-negative integer inputs whose results fit int and whose depth fits available resources.
sumTo returns an int used by the caller. countUp is void and returns no value, but produces output after each smaller call. Both retain separate local n values for active invocations.
24 | CONSTRUCT A COMPLETE ANSWER
Start with the required result and the allowed inputs. Write the direct answer for the smallest input. Then express the larger answer using one smaller result, and choose a recursive argument that approaches the base case.
Make the interface explicit: is the function returning a value, printing a sequence or changing a supplied object? Place operations before or after the recursive call according to that contract.
Finally include a complete call and expected outcome. A recursive call without a base case or a missing return path is not a complete constructed solution.
25 | TRACE A SUPPLIED PROGRAM EXACTLY
Read the base condition first, then follow the given call argument. Push a separate frame when a call begins and pause its caller at the call site. Record output immediately when a print executes.
At a return, transfer the actual returned value to the waiting caller and resume at the correct instruction. Do not assume every function uses the same base case as factorial, or every print happens during unwinding.
Label intermediate arguments, active-call state, printed output and returned results separately. They can contain different values and occur in different orders.
26 | CHECK THE WHOLE CALL CHAIN
A sound non-branching recursive program has a correct base result, a justified single recursive step, progress toward termination, and a clear use of the smaller answer or side effect.
Trace both directions: the chain of arguments reaching the base and the sequence of actions on return. Test the empty or zero case, one step from it, and several recursive levels.
These principles let you construct unfamiliar small recursive solutions, instead of memorizing one factorial program and trying to force every problem into it.