pythonadvanced10 minutes

Predict the Output of a Recursive Function with Memoization and Complex State Updates

Analyze the given Python code implementing a recursive function with memoization and state-dependent logic updates, then predict the final printed output.

Challenge prompt

Consider the following Python code that defines a recursive function `compute` with memoization. The function performs complex state changes and calls itself based on multiple conditions on its arguments. Without running the code, carefully trace the logic and determine the exact output printed when calling `compute(5, 3)`.

Guidance

• Track the memo dictionary carefully – understand when results are cached and reused.
• Follow the recursion tree closely, noting how state variables `a` and `b` evolve in each call.
• Break down the function into smaller logical units to predict each recursive call's return value.

Hints

• Pay special attention to the order of recursive calls and how the parameters change between calls.
• Note the base cases and what values they return for different inputs.
• Memoization prevents repeated calculations—try sketching the call stack and the memo dictionary entries.

Starter code

def compute(a, b, memo=None):
    if memo is None:
        memo = {}
    if (a, b) in memo:
        return memo[(a, b)]
    if a == 0:
        result = b
    elif b == 0:
        result = a
    else:
        res1 = compute(a - 1, b, memo)
        res2 = compute(a, b - 1, memo)
        if res1 % 2 == 0:
            result = res1 + res2
        else:
            result = res1 * res2
    memo[(a, b)] = result
    return result

print(compute(5, 3))

Expected output

4536

Core concepts

RecursionMemoizationState managementComplex conditionals

Challenge a Friend

Send this duel to someone else and see if they can solve it.