Search code examples
pythonrecursiongenerator

What actually happens when a recursive function is also a generator?

I am writing a function that, given an array, returns a list of possible permutations. I came up with the following and it works great:

def _permutate(elems):
    if len(elems) <= 1:
        yield elems
    else:
        for i in range(len(elems)):
            for perm in _permutate(elems[:i] + elems[i+1:]):
                yield [elems[i]] + perm

So running print(list(_permutate([2, 1, 3]))) gives me: [[2, 1, 3], [2, 3, 1], [1, 2, 3], [1, 3, 2], [3, 2, 1], [3, 1, 2]]

But I want to know what's actually happening in the background... I know a recursive function adds to a stack until it reaches it's base case and then works backwards down the stack to give you a result, and then a generator function pauses computation at it's first yield and returns a generator that you have to loop through to get the results of each yield, but I'm really confused as to what happens when you put the two together.

Rewriting the function with debug statements

def _permutate(elems):
    if len(elems) <= 1:
        print(elems) # NEW
        yield elems
    else:
        for i in range(len(elems)):
            for perm in _permutate(elems[:i] + elems[i+1:]):
                print("NEW", [elems[i]], perm)  # NEW
                yield [elems[i]] + perm

And then running

gen = _permutate([1,2,3,4,5])
print('NEXT', next(gen))
print('NEXT', next(gen))    
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))

Shows a bit clearer what's going on:

[5]
NEW [4] [5]
NEW [3] [4, 5]
NEW [2] [3, 4, 5]
NEW [1] [2, 3, 4, 5]
NEXT [1, 2, 3, 4, 5]
[4]
NEW [5] [4]
NEW [3] [5, 4]
NEW [2] [3, 5, 4]
NEW [1] [2, 3, 5, 4]
NEXT [1, 2, 3, 5, 4]
[5]
NEW [3] [5]
NEW [4] [3, 5]
NEW [2] [4, 3, 5]
NEW [1] [2, 4, 3, 5]
NEXT [1, 2, 4, 3, 5]
[3]
NEW [5] [3]
NEW [4] [5, 3]
NEW [2] [4, 5, 3]
NEW [1] [2, 4, 5, 3]
NEXT [1, 2, 4, 5, 3]
[4]
NEW [3] [4]
NEW [5] [3, 4]
NEW [2] [5, 3, 4]
NEW [1] [2, 5, 3, 4]
NEXT [1, 2, 5, 3, 4]
[3]
NEW [4] [3]
NEW [5] [4, 3]
NEW [2] [5, 4, 3]
NEW [1] [2, 5, 4, 3]
NEXT [1, 2, 5, 4, 3]
[5]
NEW [4] [5]
NEW [2] [4, 5]
NEW [3] [2, 4, 5]
NEW [1] [3, 2, 4, 5]
NEXT [1, 3, 2, 4, 5]

Found an article here that shows a table of what happens during the recursive generator. I've tried recreating this table with an array [1,2,3] enter image description here

Solution

  • I did an experiment to illustrate how the flow of the generator works:

    def _permutate(elems):
    if len(elems) <= 1:
        print(elems) # NEW
        yield elems
    else:
        for i in range(len(elems)):
            for perm in _permutate(elems[:i] + elems[i+1:]):
                print([elems[i]] + perm)  # NEW
                yield [elems[i]] + perm

# NEW
gen = _permutate([1,2,3,4,5])
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))
print('NEXT', next(gen))

    OUTPUT:

    [5]
[4, 5]
[3, 4, 5]
[2, 3, 4, 5]
[1, 2, 3, 4, 5]
NEXT [1, 2, 3, 4, 5]
[4]
[5, 4]
[3, 5, 4]
[2, 3, 5, 4]
[1, 2, 3, 5, 4]
NEXT [1, 2, 3, 5, 4]
[5]
[3, 5]
[4, 3, 5]
[2, 4, 3, 5]
[1, 2, 4, 3, 5]
NEXT [1, 2, 4, 3, 5]
[3]
[5, 3]
[4, 5, 3]
[2, 4, 5, 3]
[1, 2, 4, 5, 3]
NEXT [1, 2, 4, 5, 3]
[4]
[3, 4]
[5, 3, 4]
[2, 5, 3, 4]
[1, 2, 5, 3, 4]
NEXT [1, 2, 5, 3, 4]
[3]
[4, 3]
[5, 4, 3]
[2, 5, 4, 3]
[1, 2, 5, 4, 3]
NEXT [1, 2, 5, 4, 3]
[5]
[4, 5]
[2, 4, 5]
[3, 2, 4, 5]
[1, 3, 2, 4, 5]
NEXT [1, 3, 2, 4, 5]