B2.4.5 · Programming algorithms
Recursive algorithms
B2.4.4 explained what recursion is. This statement is about doing it: writing a recursive function from a problem description, and reading someone else's recursive function closely enough to say exactly what it does.
Explainer
What "non-branching" means here
The clearest illustration of the difference is the Fibonacci sequence, one of the classic examples every recursion textbook reaches for, precisely because it's so easy to follow: 0, 1, 1, 2, 3, 5, 8..., each term the sum of the two before it. Written directly from that definition, each call makes two further recursive calls, not one: fib(n - 1) and fib(n - 2), in the same line. That shape is called branching recursion, and this statement's own syllabus wording rules it out: "simple, non-branching recursive algorithms in programming only." A sorting algorithm that splits data into two partitions is branching in exactly the same sense, two recursive calls per case, just on a list instead of a number.
A non-branching recursive function makes exactly one recursive call inside each case. Tracing it by hand stays a straight line of winding calls, then a straight line of unwinding returns, never a tree of them.
Shape: one recursive call per case.
Shape: two or more recursive calls per case.
Fibonacci's own naive recursive definition, and splitting data for a sort, stay conceptual knowledge from B2.4.4, understanding why recursion suits them and what it costs, not something you're asked to construct or trace step-by-step at this statement.
Try it yourself
Run factorial and fib to see the difference
Both functions from the comparison above, actually running. factorial makes one recursive call per level, following a single path down to n == 1. fib makes two calls per level, so the number of calls it makes grows far faster as n increases, try changing range(10) to a bigger number and watch how quickly the list grows, and how much longer it takes.
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.
Worked example
Constructing a recursive algorithm from a problem
Isla is building a simple checksum for the raffle tickets at her school fete: add together every digit of the ticket number. Ticket 5274 should checksum to 5 + 2 + 7 + 4 = 18.
Find the base case first. A single-digit number is already its own digit sum, there's nothing left to add. So: if n < 10: return n.
Find the general case. Every other number can be split into its last digit, n % 10, and everything before it, n // 10. The digit sum of n is the last digit, plus the digit sum of what's left: exactly one recursive call, non-branching.
Write it.
def digit_sum(n): if n < 10: return n else: return n % 10 + digit_sum(n // 10)
Constructing the algorithm is choosing these three things deliberately: what makes the base case, what changes to move toward it, and what work happens at each level. Tracing it, below, is checking that choice actually behaves the way it was meant to.
digit_sum(5274)
Step 1 of 8
Winding, call 1. digit_sum(5274). Not the base case. Needs digit_sum(527) before it can add its own last digit, 4.
Winding, call 2. digit_sum(527). Needs digit_sum(52) before adding its last digit, 7.
Winding, call 3. digit_sum(52). Needs digit_sum(5) before adding its last digit, 2.
Base case reached. digit_sum(5): 5 is less than 10, so this returns 5 directly, no further call. Winding stops, unwinding begins.
Unwinding, 1st return. digit_sum(52) resumes: 2 + 5 = 7.
Unwinding, 2nd return. digit_sum(527) resumes: 7 + 7 = 14.
Unwinding, 3rd return. digit_sum(5274) resumes: 4 + 14 = 18.
Result. digit_sum(5274) = 18, exactly 5 + 2 + 7 + 4, confirming the algorithm does what Isla designed it to do.
Try it yourself
Run both functions
digit_sum from above, plus the mystery function from the next section. Try a different ticket number, or write your own single-call recursive function underneath.
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.
Worked example
Tracing code to find its purpose
Constructing goes from a problem to code. Tracing sometimes goes the other way: you're handed a function with no explanation, and asked to trace a call and then say what the function actually does. This is exactly the style of a real past-paper question, tracing a mystery function like fun(1216) and deducing its purpose from what comes out.
def mystery(n): if n < 10: return 1 else: return 1 + mystery(n // 10)
| Call | Base case? | Waiting on |
|---|---|---|
| mystery(1216) | No, 1216 ≥ 10 | 1 + mystery(121) |
| mystery(121) | No, 121 ≥ 10 | 1 + mystery(12) |
| mystery(12) | No, 12 ≥ 10 | 1 + mystery(1) |
| mystery(1) | Yes, 1 < 10 | returns 1 directly |
Unwinding: mystery(1) = 1, so mystery(12) = 1 + 1 = 2, so mystery(121) = 1 + 2 = 3, so mystery(1216) = 1 + 3 = 4.
Deducing the purpose: every call strips off one digit (n // 10) and adds exactly 1 to the running total, until the number left has only one digit. The number of times 1 gets added is the number of digits the original number had. mystery(n) counts the digits in n. 1216 has 4 digits, and the trace above returns exactly 4.
Check your understanding
Which of the following is a non-branching recursive function, in the sense this statement means it?
Common mistake
RecurringA recurring, well-documented error is losing track of the arithmetic partway through a trace, especially mixing up addition and subtraction across different levels of the same recursive call, rather than misunderstanding recursion's structure itself.
Careless mid-trace: writing "digit_sum(52) = 2 + 5 = 6" one line, having correctly worked out that digit_sum(5) returns 5, then simply adding the two numbers wrong on the way back up. The recursive structure was understood correctly, winding down, hitting the base case, unwinding back up, but a plain arithmetic slip at one level throws off every level built on top of it.
Careful mid-trace: writing out each level's own small sum explicitly, digit_sum(52) = 2 + 5 = 7, digit_sum(527) = 7 + 7 = 14, digit_sum(5274) = 4 + 14 = 18, checking each one before using it in the next line. Showing every intermediate value, not just the final answer, is also exactly what markers award credit for even when the final total is wrong.
Revision questions
Past-paper style. Write an answer, then reveal the marking points and mark yourself.
[3]Construct a recursive function power(base, exponent) that returns base raised to exponent, for a non-negative whole-number exponent, without using Python's ** operator.
Marking points
评分要点
- def power(base, exponent): if exponent == 0: return 1 (the base case).
- else: return base * power(base, exponent - 1) (the recursive case).
- Each call reduces the exponent by 1 toward 0, and the multiplications combine as the calls return.
- def power(base, exponent): if exponent == 0: return 1(基准情形)。
- else: return base * power(base, exponent - 1)(递归情形)。
- 每次调用把 exponent 减 1 朝 0 逼近,乘法在调用返回时结合。
[4]Trace the function below for the call total(4), showing the value returned at every level of the recursion.def total(n): return 0 if n == 0 else n + total(n - 1)
Marking points
评分要点
- total(4) = 4 + total(3); total(3) = 3 + total(2); total(2) = 2 + total(1); total(1) = 1 + total(0); total(0) = 0.
- Returning back up: total(0) returns 0; total(1) returns 1; total(2) returns 3; total(3) returns 6; total(4) returns 10.
- The final value returned is 10.
- total(4) = 4 + total(3);total(3) = 3 + total(2);total(2) = 2 + total(1);total(1) = 1 + total(0);total(0) = 0。
- 逐层返回:total(0) 返回 0;total(1) 返回 1;total(2) 返回 3;total(3) 返回 6;total(4) 返回 10。
- 最终返回的值是 10。
[3]State the purpose of the function below, justifying your answer by reference to a trace of reverse_str("cats").def reverse_str(s): return s if len(s) <= 1 else reverse_str(s[1:]) + s[0]
Marking points
评分要点
- The function returns its input string reversed.
- Trace reverse_str(cats): reverse_str(ats) + c; reverse_str(ats) = reverse_str(ts) + a; reverse_str(ts) = reverse_str(s) + t; reverse_str(s) returns s (length 1, base case).
- Combining back up: s -> st -> sta -> stac, so reverse_str(cats) returns stac, which is cats reversed.
- 该函数返回其输入字符串的反转。
- 追踪 reverse_str(cats):reverse_str(ats) + c;reverse_str(ats) = reverse_str(ts) + a;reverse_str(ts) = reverse_str(s) + t;reverse_str(s) 返回 s(长度为 1,基准情形)。
- 逐层结合:s -> st -> sta -> stac,所以 reverse_str(cats) 返回 stac,即 cats 的反转。
Flashcards
Active recall for this statement’s key terms.
Keep this statement’s practice with you
Free account: unlock every revision question and flashcard for B2.4.5, and every other IB CS 2027 statement.