Preview

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

Recursive functions

A recursive function calls itself to solve a smaller or simpler version of the same problem. It needs a stopping condition, usually called the base case, and each new call must move towards it. Recursion is useful for structures such as nested folders, trees and menus.

By the end, you will be able to

identify a base case and a recursive case
explain how an input moves towards the base case
trace new calls on the way down and returned values on the way back
write and repair a short recursive function

Predict before the model

Read the question below before viewing the call-stack diagram. Treat each function call as a separate invocation with its own parameter value. Decide whether the current call can finish before the returned value from the smaller call is available.

Multiple choice1 mark

When pattern_total(2) needs the result of pattern_total(1), what must happen?

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.

Two cases and two directions

A recursive function needs two connected parts:

the base case handles the simplest input, returns a value without making another recursive call, and starts the return phase;
the recursive case changes the input and calls the function again, making measurable progress towards the base case.

Calls are created on the way down. Each waiting call has a call-stack frame that keeps its parameter, local variables, return address and unfinished calculation. When the base case returns, those waiting calls complete in reverse order as the results unwind. A base case that is never reached does not prevent infinite recursion.

Worked trace: calls first, answers later

For pattern_total(3), do not jump straight to 6. Record the two phases separately.

Calls descend

pattern_total(3) waits for pattern_total(2)
pattern_total(2) waits for pattern_total(1)
pattern_total(1) waits for pattern_total(0)
pattern_total(0) returns 0 without another call

Results unwind

pattern_total(1) returns 1 + 0 = 1
pattern_total(2) returns 2 + 1 = 3
pattern_total(3) returns 3 + 3 = 6

The base case does more than 'end the program': it prevents another self-call for the simplest input and provides the first value used while earlier calls return.

Multiple choice1 mark

What does the base case do when its condition is met?

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 answer4 marks

Explain why pattern_total(4) terminates. Then state the order in which values are returned while the waiting calls unwind.

Connect the changing parameter to the base case, then describe the return phase separately.

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 version terminates: def count_down(n): return [n] + count_down(n - 1). For n <= 0, the result should be an empty list.

Write the complete two-case function. Your explanation must identify progress and the point at which no further self-call is made.

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.