15

15 — Practice solutions

← Questions

These are independently written explanations, not an official marking scheme.

15A

def power(a, b):
    if b == 0:  # Multiplicative base value: a**0 is 1 under this contract.
        return 1
    return a * power(a, b - 1)  # Multiply after the smaller power returns.

Calls have b=3,2,1,0; returned values are 1 at b=0, then 3,9,27. Negative b decreases away from zero, eventually causing excessive recursion in Python. Reject negative b if the contract only permits nonnegative exponents.

Reasoning

Exponent b counts how many multiplications by a remain. Reducing b by 1 makes progress for nonnegative integers. At b=0, return1 so multiplication by the base result leaves the product unchanged; returning0 would make every positive power zero.

15B

recur(1)=3; recur(2)=5; recur(3)=9; recur(4)=17.

def recur_iterative(n):
    result = 3  # Already represents recur(1).
    for step in range(2, n + 1):  # One update for each value from 2 through n.
        result = 2 * result - 1
    return result

For n=1 the loop runs zero times and returns the correct base value. This function assumes n≥1, as specified.

Reasoning

The base is at n=1, so n=4 requires three recurrence updates, not four. During return, apply the entire expression 2 * previous - 1; do not subtract1 from the argument instead. Iteration stores the previous result explicitly.

15C

P(0)=False, P(1)=True, P(2)=False, P(3)=True, P(4)=False. It tests whether a nonnegative integer is odd. The stack retains each unfinished call’s state and continuation; after the base returns, each caller applies not to the returned Boolean before returning to its own caller.

Reasoning

Each call reverses the previous Boolean. Trace from False at 0, alternating True/False. The pattern is parity, not whether n is positive. Explain the stack through saved local state and return locations, rather than saying only that it “stores the function”.

15D

3 10
12 12

The first assignment changes a local binding. global score makes the second function update the module binding. Removing it causes UnboundLocalError: augmented assignment tries to read a local score before that local has a value.

def add_two(value):
    return value + 2

15E

branches(4) → 3
├─ branches(3) → 2
│  ├─ branches(2) → 1
│  │  ├─ branches(1) → 1
│  │  └─ branches(0) → 0
│  └─ branches(1) → 1
└─ branches(2) → 1
   ├─ branches(1) → 1
   └─ branches(0) → 0

9 calls; maximum 4 active frames. Add child returns to calculate each parent return. The call tree records all invocations; the stack holds only the current unfinished path.