Predict the Output of a Recursive Memoization with Mutable Default Argument
Analyze a Python function that uses recursion combined with mutable default arguments and memoization, then predict the exact printed output when the function is called.
Challenge prompt
Consider the following Python function `complex_sequence`. It recursively computes values using memoization but also uses a list as a mutable default argument. Predict the exact printed output after the function call `complex_sequence(5)`. Explain the reasoning behind the output including the role of the mutable default argument and recursion steps.
Guidance
- • Examine how mutable default arguments behave in recursive function calls.
- • Understand the memoization dictionary and how it stores intermediate results.
- • Trace the recursion depth and values returned at each step carefully.
Hints
- • Mutable default arguments retain changes across all recursive calls within the same invocation.
- • Memoization dictionary keys correspond to specific input values for which results are cached.
- • Focus on how the `history` list is updated and printed during recursion.
Starter code
def complex_sequence(n, memo={}, history=[]):
if n in memo:
history.append(memo[n])
print(f'Using cached value for {n}: {memo[n]}, history: {history}')
return memo[n]
if n <= 1:
memo[n] = n
history.append(n)
print(f'Base case for {n}, history: {history}')
return n
result = complex_sequence(n - 1, memo, history) + 2 * complex_sequence(n - 2, memo, history)
memo[n] = result
history.append(result)
print(f'Computed value for {n}: {result}, history: {history}')
return result
complex_sequence(5)Expected output
Base case for 1, history: [1] Base case for 0, history: [1, 0] Computed value for 2: 1, history: [1, 0, 1] Using cached value for 1: 1, history: [1, 0, 1, 1] Computed value for 3: 3, history: [1, 0, 1, 1, 3] Using cached value for 2: 1, history: [1, 0, 1, 1, 3, 1] Using cached value for 1: 1, history: [1, 0, 1, 1, 3, 1, 1] Computed value for 4: 5, history: [1, 0, 1, 1, 3, 1, 1, 5] Using cached value for 3: 3, history: [1, 0, 1, 1, 3, 1, 1, 5, 3] Computed value for 5: 11, history: [1, 0, 1, 1, 3, 1, 1, 5, 3, 11]
Core concepts
Challenge a Friend
Send this duel to someone else and see if they can solve it.