A Level Computer Science 9618: Tracing a Recursive Function's Call Stack

A programmer writes the following recursive function to add together the individual digits of a positive integer.

FUNCTION SumDigits(N : INTEGER) RETURNS INTEGER
    IF N < 10 THEN
        RETURN N
    ELSE
        RETURN (N MOD 10) + SumDigits(N DIV 10)
    ENDIF
ENDFUNCTION

The statement OUTPUT SumDigits(4831) is then executed.

(a) State the base case and the general (recursive) case of this function, and explain the purpose of each. [2]

(b) Complete a trace of the calls placed on the call stack, in the order they are called, when SumDigits(4831) is evaluated, and state the value returned by each call once the base case is reached. [4]

(c) State the value output by OUTPUT SumDigits(4831), and explain why expressing this algorithm recursively is appropriate for this problem. [2]

Part (a): The base case and the general case

A recursive routine must always have two parts:

Base case, IF N < 10 THEN RETURN N. When N is already a single digit, its digit sum is simply itself, so the function returns immediately without calling itself again. This is what eventually stops the recursion.
General (recursive) case, RETURN (N MOD 10) + SumDigits(N DIV 10). N MOD 10 extracts the last digit of N, and N DIV 10 removes that digit, leaving a smaller number. The function calls itself with this smaller number and adds its result to the extracted last digit.

[2 marks]: [1] for correctly identifying and describing the base case, [1] for correctly identifying and describing the general case.

Part (b): Tracing the call stack

Each call to SumDigits is placed on the call stack until the base case is reached, at which point the calls “unwind”, each one completing and returning its value to the call that invoked it.

Building the stack (calls made, in order):

Call pushed	N	N < 10 ?	What happens
1	`SumDigits(4831)`	No	Needs `SumDigits(483)`; will add `4831 MOD 10 = 1` once it returns
2	`SumDigits(483)`	No	Needs `SumDigits(48)`; will add `483 MOD 10 = 3` once it returns
3	`SumDigits(48)`	No	Needs `SumDigits(4)`; will add `48 MOD 10 = 8` once it returns
4	`SumDigits(4)`	Yes	Base case reached: `RETURN 4`

Unwinding the stack (calls returning, in reverse order):

Call returning	Calculation	Value returned
`SumDigits(4)`	base case	4
`SumDigits(48)`	`8 + 4`	12
`SumDigits(483)`	`3 + 12`	15
`SumDigits(4831)`	`1 + 15`	16

[4 marks]: [1] for correctly listing the four calls pushed onto the stack in order, [1] for correctly identifying that SumDigits(4) is the base case that starts the unwinding, [2] for correctly unwinding the additions (8 + 4 = 12, 3 + 12 = 15, 1 + 15 = 16).

Part (c): Final value and why recursion suits this problem

OUTPUT SumDigits(4831) outputs 16. This can be checked directly: the digits of 4831 are 4, 8, 3 and 1, and 4 + 8 + 3 + 1 = 16, matching the traced result.

Recursion is appropriate here because the problem of “find the digit sum of N” can be restated as a smaller version of exactly the same problem: “find the digit sum of N DIV 10”, plus the one extra digit N MOD 10. Since this smaller problem eventually shrinks down to a single digit (the base case), the function is guaranteed to terminate, and each level only needs to solve a slightly smaller instance of the same task.

[2 marks]: [1] for the correct output value 16, [1] for a valid explanation referring to the problem being defined in terms of a smaller version of itself.

Final answers

(a) Base case: N < 10 → RETURN N. General case: RETURN (N MOD 10) + SumDigits(N DIV 10).
(b) Calls pushed: SumDigits(4831) → SumDigits(483) → SumDigits(48) → SumDigits(4). Returns while unwinding: 4 → 12 → 15 → 16.
(c) Output = 16.