pythonadvanced10 minutes

Predict the Output of a Recursive Generator with Complex State

Analyze the output of a Python function that uses recursion, generators, and mutable state to yield a sequence of numbers based on intricate control flow.

Challenge prompt

Consider the following Python function that recursively generates a sequence of numbers using a generator and a mutable dictionary as state. What will be the printed output when the function run_sequence(3, {}) is called and fully iterated? Analyze carefully how the function manages its state and the order in which numbers are yielded. Provide the exact output sequence as a list of integers separated by spaces.

Guidance

• Focus on how recursive calls affect the shared mutable dictionary state.
• Follow the generator's yield sequence carefully, considering the order of yielding before and after recursion.
• Remember Python generators pause at yield statements and resume where they left off.

Hints

• Trace through the calls starting from n=3 down to n=0 to see how the state dictionary changes.
• Note when the function yields values around the recursive calls (before or after).
• Pay attention to the key 'count' in the state dictionary and how it increments.

Starter code

def run_sequence(n, state):
    if 'count' not in state:
        state['count'] = 0
    if n == 0:
        yield 0
        return
    state['count'] += 1
    yield state['count']
    yield from run_sequence(n-1, state)
    state['count'] += 1
    yield state['count']

print(' '.join(str(x) for x in run_sequence(3, {})))

Expected output

1 2 3 0 4 5 6

Core concepts

recursiongeneratorsmutable stateyield behavior

Challenge a Friend

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