IB COMPUTER SCIENCE | B2.4.5 Recursive Algorithms (HL)

Lesson objective

Construct and trace simple non-branching recursive algorithms, following local state, base cases, pending operations, printed output and returned results.

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.

MATCH THE RECURSIVE PROGRAM IDEA

Terminology

Terminology

Non-branching recursion

A recursive call pattern with at most one recursive call per invocation.

Base case

A case completed without another recursive call on that path.

Recursive step

The reduction and work connecting an input to a smaller similar problem.

Contract

The agreed inputs, results, errors and side effects.

Precondition

A requirement assumed for valid use of a function.

Input domain

The set of permitted inputs.

Recursive argument

The value supplied to the next recursive call.

Progress measure

A quantity that moves toward termination, such as remaining items.

Call entry

Beginning a new invocation with its own local state.

Caller

The invocation or code waiting for a called function to finish.

Call site

The place where a function is invoked and execution later resumes.

Stack frame

Retained state for an active function invocation.

Local parameter

A parameter binding belonging to one invocation.

Pending operation

Work awaiting the recursive result.

Descent

Entering the chain of smaller recursive calls.

Unwinding

Completing waiting calls as results return.

Returned result

The value supplied back to the calling expression.

Printed output

Text displayed as a side effect rather than a returned result.

Bare return

Python return without an expression, supplying None.

Implicit return

Reaching the end of a Python function and returning None.

Empty sum

The sum of no terms, defined as 0.

Factorial base

0! = 1, supporting the recursive product.

Integer division

Whole-number division used here to remove a decimal digit.

Modulo

Remainder operation, used here to obtain the last decimal digit.

Near-base test

An input needing one step before reaching the base case.

Trace table

An organized record of actual algorithm actions and state.

Wrapper

An entry function that can validate before delegating to a helper.

Recursion depth

The length of the simultaneously active recursive call chain.

Auxiliary space

Extra working storage beyond input under a stated model.

Tail-recursive call

A recursive call with no additional work remaining after it returns.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which describe non-branching recursion here?
2. Which are correct for sum_to(4)?
3. Which distinguish a local parameter from a returned result?
4. Which are correct for countdown(3) with print before the call?
5. Which are correct for count_up(3)?
6. Which describe power(3, 4)?
7. Which describe digit_sum(472)?
8. Which keep recursive list summation correct?
9. Which are useful tests?
10. Which resource statements are correct under the stated model?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Construct sum_to(n) for non-negative integer n.

2. Trace the returned values of sum_to(3).

3. Explain why factorial uses 1 rather than 0 as its base result.

4. Trace countdown(3) when printing occurs before the recursive call.

5. Trace count_up(3) when printing occurs after the recursive call.

6. Construct a recursive power function for a numeric base and non-negative integer exponent.

7. Trace digit_sum(472).

8. Explain why increasing an index can still make progress toward a recursive base case.

9. Construct a non-branching recursive count of matching list values.

10. Explain the effect of omitting the return of a computed recursive result in Python.

11. Describe a trace table that separates call arguments from results and output.

12. Compare recursive and iterative summation under the unit-cost model.

CONSTRUCT AND TRACE | SUM THE EVEN TERMS

Construct a non-branching recursive function that returns the sum of the even integers from 2 to n, where n is a non-negative even integer. Then trace the call with n = 6, separating call arguments from returned values. State how the contract avoids negative or odd inputs.

Reveal a solution
def even_sum(n):
    if n == 0:
        return 0
    return n + even_sum(n - 2)

print(even_sum(6))

The precondition is that n is a non-negative even integer; a wrapper can reject other inputs before entry. Arguments descend 6, 4, 2, 0. Results return 0, 2, 6, 12, and the caller prints 12. The smaller argument decreases by 2 because the required terms are even.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

Selections are kept while this page is open.

Workbook

Workbook

COMING SOON

The workbook for B2.4.5 Recursive Algorithms (HL) is coming soon. Complete the matching task and written questions in your exercise book.