B2.4.5 Construct and trace recursive algorithms in a programming language. (HL only)

📚 You can find additional information in the course companion pages 404 to 406

The Big Idea

Recursion becomes powerful when we understand how it operates at runtime. This standard asks you to construct a recursive function and trace it — that means recording the values of key variables at each stage of execution.

A simple, non-branching recursive algorithm means:

• There’s one recursive call per execution (not multiple branches).
• The logic is linear, and does not involve choosing between multiple recursive paths.

---

Example 1: Recursive Sum of Natural Numbers

Problem: Given a positive integer n, compute the sum of all natural numbers up to n.

Code:

def recursive_sum(n):
    if n == 1:
        return 1
    return n + recursive_sum(n - 1)

Call:

result = recursive_sum(4)

Trace Table:

Call Stack	n Value	Returned
sum(4)	4	4 + sum(3) → 10
sum(3)	3	3 + sum(2) → 6
sum(2)	2	2 + sum(1) → 3
sum(1)	1	1

---

Example 2: Recursive String Reversal

Problem: Reverse a string recursively.

Code:

def reverse_string(s):
    if len(s) <= 1:
        return s
    return s[-1] + reverse_string(s[:-1])

Call:

result = reverse_string("cat")

Trace Table:

Call Stack	s	Returned
reverse_string("cat")	"cat"	"t" + reverse("ca") → "tac"
reverse_string("ca")	"ca"	"a" + reverse("c") → "ac"
reverse_string("c")	"c"	"c"

---

Example 3: Recursive Power Function

Problem: Compute x^n where n is a non-negative integer.

Code:

def power(x, n):
    if n == 0:
        return 1
    return x * power(x, n - 1)

Call:

result = power(2, 3)

Trace Table:

Call Stack	x	n	Returned
power(2, 3)	2	3	2 * power(2,2) = 8
power(2, 2)	2	2	2 * power(2,1) = 4
power(2, 1)	2	1	2 * power(2,0) = 2
power(2, 0)	2	0	1

---

Summary

These three examples show:

• A simple base case and one non-branching recursive step.
• A clear, predictable call structure.
• Easy-to-trace variable changes in a tabular format.

To construct and trace means not only writing the function but also being able to record or simulate its behavior at runtime. In IB exams, this is often done via trace tables, just like the ones shown here.