pythonadvanced10 minutes

Predict Output for Recursive State Machine with Complex Memoization

Analyze a recursive function that behaves like a state machine with memoization to predict the final output of given input values.

Challenge prompt

Given the Python function below, predict the exact output when the function `state_machine(10)` is called and its return value is printed. Explain your reasoning regarding the recursion, memoization, and state transitions made by the function.

Guidance

• Carefully track the recursive calls and the memoization cache to understand repeated calls.
• Observe how the state changes based on conditions and how values are combined in recursion.
• Consider edge cases of the input values and how base cases influence the recursion outcome.

Hints

• Focus on how the cache dictionary stores results and prevents re-computation.
• Examine the conditions that change the state and how that affects recursive depth and return values.

Starter code

def state_machine(n, state=0, cache={}):
    if (n, state) in cache:
        return cache[(n, state)]
    if n == 0:
        return 1 if state == 0 else 0
    if state == 0:
        result = state_machine(n - 1, 0, cache) + 2 * state_machine(n - 1, 1, cache)
    elif state == 1:
        result = 3 * state_machine(n - 1, 0, cache) + state_machine(n - 1, 2, cache)
    else:
        result = state_machine(n - 1, 2, cache) + state_machine(n - 1, 0, cache)
    cache[(n, state)] = result
    return result

print(state_machine(10))

Expected output

6831

Core concepts

recursionmemoizationstate machinedynamic programming

Challenge a Friend

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