A Fibonacci sequence is a series of numbers formed by adding together the two preceding numbers, for example: 0, 1, 1, 2, ... This function calculates and returns values in the Fibonacci sequence and uses recursion. FUNCTION Fib(Number : INTEGER) RETURNS INTEGER IF Number <= 1 THEN Result ← Number ELSE Result ← Fib(Number - 1) + Fib(Number - 2) ENDIF RETURN Result ENDFUNCTION Complete the trace table for the function when it is called as Fib(5).

Mark scheme

Marking points from the official mark scheme (May/June 2023). The mark or mark type is shown in brackets.

1. [1] A process using a function or procedure defined in terms of itself / calls itself.
2. [1] A recursive process must have a base case (which is a way to return without making a recursive call) // terminating solution // concept of unwinding described
3. [1] There must (also) be a general case where the recursive call takes place.
4. [1] Call number column correct
5. [1] Function call and Number columns correct
6. [1] Result column down to base case (Winding) rows 1–6 correct
7. [1] Result column down from base case (Unwinding) rows 7–10 correct
8. [1] Return value column correct