15 Python Chapter 4 — functions and recursion

Python Chapter 4 — functions and recursion

← Index · Solutions

Priority key · Priorities guide emphasis; they do not remove taught scope.

Exam recall

Each call has local state. Trace descent and unwinding. A base case must be reachable; distinguish local rebinding, global rebinding and object mutation.

Function contracts, parameters and state priority/medium

caller: answer = mystery(3)
                  ↓ argument 3 is bound to this call's local n
function: compute a result, then RETURN it
                  ↓ returned value is assigned to answer

The caller pauses while the called function runs. A nested call adds another pause: its caller cannot finish an expression using the result until that result exists. This is ordinary function behaviour; recursion repeatedly applies it to the same function definition with new local state.

A parameter is a name in a function definition; an argument is a value supplied in a call. Local variables belong to that invocation. Return supplies a result to the caller and ends the function. A function reaching its end without a return value returns None. Printing produces output but does not substitute for returning the requested result.

Python passes object references by assignment. Rebinding a local parameter does not rebind the caller’s name; mutating a shared list object can change what the caller sees. Prefer clear parameters and return values over hidden global changes. Multiple returned values are packaged as a tuple, which can be unpacked by the caller.

Local and global names: trace the bindings priority/high

A local variable is bound within a function invocation. A global variable is bound at module level. An unshadowed global can be read inside a function. Assignment inside a function normally binds a local name; global name makes assignment target the module-level binding. Local and global names with the same spelling need not be the same binding.

score = 10
 
def local_change():
    score = 3
    return score
 
def global_change():
    global score
    score += 2
    return score
 
print(local_change(), score)
print(global_change(), score)

Expected output: 3 10, then 12 12. The first function changes only its local binding. The second changes the global binding. Without global score, the second function’s score += 2 attempts to use a local name before it has a value, raising UnboundLocalError.

Recursion requires two ideas priority/high

1. A base case answers a small case without another recursive call.
2. A recursive case transforms the problem into a smaller one and combines its result. Progress must move towards the base case for all valid inputs.

Each unfinished call has its own state on the call stack, including local values and where execution must continue. The last call entered finishes first. You must trace both descent and return/unwinding.

Worked example — calls and returns priority/high

def mystery(n):
    if n == 0:  # Base case completes without another call.
        return 0
    return n + mystery(n - 1)  # Add n only after the smaller call returns.

For nonnegative integers, this computes 1+2+…+n. In mystery(3), writing return 3 + mystery(2) does not return 3 immediately.

Descent: mystery(3) waits for 3 + mystery(2)
         mystery(2) waits for 2 + mystery(1)
         mystery(1) waits for 1 + mystery(0)
Base:    mystery(0) returns 0
Unwind:  mystery(1) returns 1 + 0 = 1
         mystery(2) returns 2 + 1 = 3
         mystery(3) returns 3 + 3 = 6

For −1, repeatedly subtracting 1 moves away from zero. Python will eventually raise RecursionError when recursion is too deep; the actual program does not run forever. A base case can exist in the code yet still be unreachable for a particular input.

A recursive call returns one result to its caller; the caller then performs its deferred calculation. In the trace, the values 3,2,1,0 are arguments on descent, not the four final answers.

Paused frame	Local n	Work waiting after the inner call
mystery(3)	3	Add 3 to the returned value.
mystery(2)	2	Add 2 to the returned value.
mystery(1)	1	Add 1 to the returned value.

The base frame needs no further call. The most recently paused frame resumes first, which is why the call stack has LIFO behaviour.

Recursion can express recursively defined problems clearly, but calls consume stack space and incur overhead. Iteration stores progress in explicit loop state and avoids growing recursive depth for the equivalent calculation. Do not claim recursion is always worse or always faster.

Adapting safely priority/high

State the input domain. For factorial, base 0! = 1; for a sum, base sum(0) = 0. Copying the wrong base value changes every return. Trace n=0, n=1 and a small larger n before generalising. If the function returns a Boolean, track Boolean operations during unwinding instead of treating the result as a numeric sum.

Branching calls: draw each invocation priority/high

def branches(n):
    if n <= 1:
        return n
    return branches(n - 1) + branches(n - 2)

Read the edges downward for calls and the return labels upward for results. Five calls occur in total; the maximum simultaneous depth is three frames for this function. Repeated arguments still represent separate calls.

Practice

Exam focus: recursion/call stacks recur in HCI 2022 modified Q3,2023 Q3,2024 Q4,2025 Q7 and ASRJC 2025 Q1. Use the original 2025 Q7, PDF p.6 alongside 15B, and ASRJC 2025 Q1, p.2 alongside 15A. The originals include explanation parts as well as calculations.

Handwritten trace: write call arguments down to the base, then return values upwards. Record the pending operation explicitly. For recursive-to-iterative conversion, identify the base result, one recurrence update and how many updates are needed.

15A — adapted from ASRJC 2025 Q1. Define power(a, b) recursively for an integer b ≥ 0, with base power(a, 0) = 1. Trace power(3, 3) including returns. Explain the problem with negative b under repeated subtraction.

15B — adapted from HCI 2025 Q7. A function has recur(1) = 3 and recur(n) = 2 * recur(n - 1) - 1 for n > 1. Trace recur(4) and write an iterative function with the same result for integers n ≥ 1.

15C — adapted from HCI 2023 Q3, extra practice. P(0) is False and P(n) is not P(n-1) for n > 0. Find P(3) and P(4), describe what P tests, and explain the role of the call stack.

Hints

Write the base result first when unwinding. 15B: each loop iteration applies the recurrence once, starting from the n=1 value.

15D — original, scope trace. Without running the local/global example, give its two output lines. Explain the role of global score and the error caused by removing it from global_change. Rewrite the increment as add_two(value) without global mutation.

15E — original, recursion tree. Draw the complete call tree for branches(4). Label the arguments and returned values. State the total calls and the greatest number of simultaneously active branches frames.

Revision checklist

• 15.1 Define and call functions with the required parameters and return values.
• 15.2 Distinguish parameters, arguments, local variables and global variables.
• 15.3 Explain the effect of mutating an argument versus rebinding a local name.
• 15.4 Trace nested calls and the point at which each function returns.
• 15.5 Identify a base case and a recursive step that makes progress.
• 15.6 Draw call-and-return traces or recursion trees, including deferred calculations.
• 15.7 Explain the role of stack frames, local state and return locations.
• 15.8 Compare recursion and iteration in context and explain recursion-depth failure.
• 15.9 Convert a simple recursive algorithm to an iterative version.
• 15.10 Test base cases and the smallest recursive case separately.

Visual revision mindmap

Open this mindmap and its text version · All 21 mindmaps

Your mindmap framework

Centre: Python Chapter 4 — functions and recursion. Build the six branches below. For each subbranch, add a short definition, a labelled sample and one exam trap from memory; then check the chapter.

flowchart LR
    C["15 • Revision map"]
    C --> B0["Function interface"]
    C --> B1["Scope and shared objects"]
    C --> B2["Recursive design"]
    C --> B3["Call stack"]
    C --> B4["Compare and translate"]
    C --> B5["Visual checks and mistakes"]

• Function interface

  • Definition versus call.
  • Parameter versus argument.
  • Return value versus printed output.
  • None when no value returned; tuple for multiple results.

• Scope and shared objects

  • Local binding per invocation.
  • Module-level global binding.
  • Reading versus shadowing versus global rebinding.
  • Mutating shared object versus rebinding local parameter.

• Recursive design

  • State the valid input domain.
  • Base case and base result.
  • Recursive step makes progress.
  • Combine the smaller result correctly.

• Call stack

  • One frame per unfinished invocation.
  • Arguments/local values and continuation.
  • Descent pauses the caller.
  • Unwinding resumes the most recent unfinished caller.

• Compare and translate

  • Recursive relation → initial iterative result.
  • Number of updates and bounds.
  • Clarity, call overhead and stack space.
  • RecursionError when depth becomes excessive.

• Visual checks and mistakes

  • Draw scope boxes with separate score bindings.
  • Draw call tree with arguments and returns.
  • Count all calls separately from maximum active depth.
  • Avoid: return n before inner call finishes; unreachable base; wrong base value.

Close the notes and test the map: explain one branch aloud, sketch its sample, then answer a linked practice question. Mark any missing link to revisit.

Source trail

9569 §§1.2.3–1.2.4,1.4; school Functions.

HCI 2022 Q3; 2023 Q3; 2024 Q4; 2025 Q7.

Source guide records provenance and original-paper locations.