Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Recursive functions

Nested structures and self-similar patterns can be solved by reducing a problem to a smaller version of itself.

By the end, you will be able to

identify base and recursive cases
show progress towards termination
trace calls downward and returns upward
write and repair a short recursive function

Reactivate: calling a function and using its returned value.

Two cases and two directions

The base case returns a result without another self-call. The recursive case calls the function with a smaller or simpler input. Calls descend until the base case, with each waiting call retaining its own parameter and unfinished work. Returned values then travel back in the opposite direction as the calls unwind.

Do not trace only the downward calls: OCR questions may require the final value, which depends on the return phase.

Multiple choice1 mark

Before seeing the call-stack model, what must happen when pattern_total(2) needs the result of pattern_total(1)?

AThe call with 2 finishes before the call with 1 starts.
BBoth calls share one parameter value.
CThe base case is skipped.
DThe call with 2 waits while a new call with 1 is evaluated.

Worked model: calls first, answers later

For total(n), each call with n > 0 waits for total(n − 1). At n = 0 the base case returns immediately. Only then can pending additions finish from the deepest call outward.

Write traces in two phases: descent (parameters and new calls) then unwinding (returned values). A valid recursive case must make measurable progress to the base case.

Multiple choice1 mark

What is the main purpose of a base case?

AIt stops further recursive calls for the simplest input.
BIt makes every call use a loop.
CIt stores all parameters globally.
DIt guarantees constant memory use.

Trace table10 marks

Trace the calls and returned values.

Enter a value only when it changes. Keep the listing's order.

Use one row for each pass through the loop. Fill in a box only when that value changes on that row, and leave the rest blank.

ProgramPython

def pattern_total(n):
if n == 0:
return 0
return n + pattern_total(n - 1)
answer = pattern_total(4)
print(answer)

Trace table with 6 columns
Row	n (pattern_total)	answer	Return value	Depth	n == 0	Output
1
2
3
4
5
6
7
8
9
10
11
12

Written answer3 marks

Explain why pattern_total(4) terminates and state the order in which the additions are completed while calls return.

Refer to the changing parameter and the base case.

Students type their answer here.

Write a recursive digit sum

Return the sum of the decimal digits in a non-negative integer. Use n % 10 for the final digit and n // 10 for the remaining digits.

Coding task5 marks

def digit_sum(n):
    # Base case, then recursive case.
    pass

Written answer4 marks

Repair this broken recursion, then explain why your repair terminates: def count_down(n): return [n] + count_down(n - 1). Write a suitable base case and corrected function body.

For n <= 0 the result should be an empty list. Then link decreasing n to the stopping condition.

Students type their answer here.

Checkpoint

Complete the safe-recursion explanation from memory. There is no answer bank, and correctness is withheld until teacher review.

Fill in the blanks4 marks

A recursive function calls checkpoint gap 1. Its checkpoint gap 2 case returns without another recursive call. Each recursive case must make checkpoint gap 3 towards that case. Returned results are combined as calls checkpoint gap 4.

Review your understanding

Before submitting, check that you can explain the main distinction in your own words, apply it in an unfamiliar context and justify the resulting behaviour or consequence.