CODEWITHSUNDEEP
pythonrecursioncallstack
Ramu
Ramu

Reputation: 67

Recursive stack in Python

I am trying to understand call stack for the below python recursive function. The function gives all the combinations for a given set.

def subsets(A):
    if not A:
        yield []
    else:
        for s in subsets(A[1:]):
            yield s
            yield [A[0]] + s
l1=[1,2,3]
print(list(subsets(l1)))

The program is generating the output as desired:

[[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

However I am not able to visualize the call stack. How is it able to print [1,2,3]? To my understanding as follows

call stack 1 : values are : for s in [2,3], a[0] = 1, a = [1,2,3]
call stack 2 : values are : for s in [3], a[0] = 2, a = [2,3]
call stack 3 : values are : for s in [], a[0] = 3, a = [3]

Can some help me to understand call stack flow with s and a values?

Upvotes: 5

Views: 208

Answers (3)

Arne
Arne

Reputation: 10545

You call list() on a generator. This will call the generator again and again, until it is exhausted. Let's track the flow of execution. This can be a good exercise to understand generators. I'll format everything as a code block, so that I can use proper indentation to clarify the hierarchy of generator calls.

subsets([1, 2, 3]) is called, 
    so A is [1, 2, 3]. 
    This list is not empty, so the else block is executed.
    A[1:] is [2, 3], so to determine the first s,
    subsets([2, 3]) is called.
        Now A is [2, 3], so A[1:] is [3], so to determine s,
        subsets([3]) is called.
            Now A is [3], so A[1:] is [], so to determine s,
            subsets([]) is called.
                Now A is [], so the if block is executed.
                This yields [].
            The loop starts with s = [].
            This yields [] again.
        Now this loop starts, also with s = [],
        because this is what subsets([3]) has just yielded.
        So this yields [] as well.
    So subsets([2, 3]) has yielded [], 
    so this loop also starts with s = [].
    This yields [] yet again.
So subsets([1, 2, 3]) has yielded [], 
and now this generator is called again (because of list()), 
    picking up the action after the previously executed yield statement.
    So we reach the next statement: yield [A[0]] + s.
    This yields [1].
subsets([1, 2, 3]) is called again,
    picking up at the end of the first run through the for loop,
    so to determine the next s, 
    subsets([2, 3]) is called again, 
        picking up at yield [A[0]] + s.
        This yields [2].
    So the loop starts again, with s = [2].
    This yields [2].
subsets([1, 2, 3]) is called again,
    picking up at yield [A[0]] + s, with s = [2].
    This yields [1, 2].
subsets([1, 2, 3]) is called again,
    picking up at the end of the for loop,
    so to determine the next s, 
    subsets([2, 3]) is called again,
        picking up at the end of the for loop,
        so to determine the next s,
        subsets([3]) is called again, 
            picking up at yield [A[0]] + s.
            This yields [3].
        So the loop starts again, with s = [3].
        This yields [3].
    So the loop starts again, with s = [3].
    This yields [3].
subsets([1, 2, 3]) is called again,
    picking up at yield [A[0]] + s, with s = [3].
    This yields [1, 3].
subsets([1, 2, 3]) is called again,
    picking up at the end of the for loop,
    so to determine the next s, 
    subsets([2, 3]) is called again,
        picking up at yield [A[0]] + s, with s = [3].
        This yields [2, 3].
    So the loop starts again, with s = [2, 3].
    This yields [2, 3]. 
subsets([1, 2, 3]) is called again,
    picking up at yield [A[0]] + s, with s = [2, 3].
    This yields [1, 2, 3].
subsets([1, 2, 3]) is called again,
    picking up at the end of the for loop,
    so to determine the next s, 
    subsets([2, 3]) is called again,
        picking up at the end of the for loop,
        so to determine the next s, 
        subsets([3]) is called again, 
            picking up at the end of the for loop,
            so to determine the next s, 
            subsets([]) is called again, 
                picking up at the end of the if block,
                so we reach the end of the generator, 
                which means it is exhausted and yields nothing anymore.
            So there is no further iteration of the for loop,
            hence subsets([3]) is also exhausted.
        So subsets([2, 3]) is also exhausted.
    So subsets([1, 2, 3]) is also exhausted.

Upvotes: 1

blue note
blue note

Reputation: 29099

This is a direct implementation of the mathematical definition of the powerset

An empty A has no subsets (yield []).

For the non-empty, you have two options

  1. keep the first element, and concatenate all possible subsets of the rest (yield [A[0]] + s)

  2. do not keep the first element, and return the possible subsets of the rest (yield s)

So, with A = [1, 2, 3] you have the union of [1] + subsets([2, 3]) and subsets([2, 3]). Similarly, subsets([2, 3]) is union of [2] + subsets([3]) and subsets([3]). finally, subsets([3]) is [] or [3]. That gives 3 steps, with 2 possible outcomes on each, giving the 8 possible combinations.

Upvotes: 1

Booboo
Booboo

Reputation: 44313

When you call susbsets initially, argument A is [1, 2, 3]. The important thing to note is that the function will recurse repeatedly calling itself with arguments [2, 3], [3] and [] before it starts yielding values for the current argument, [1, 2, 3]. Then all these recursive calls return and we execute the the following code with A having the value [1, 2, 3]:

for s in subsets(A[1:]):
    yield s # produces [2, 3]
    yield [A[0]] + s # produces [1, 2, 3]

So we would expect the last two values yielded to be [2, 3], [1, 2, 3] within the containing list.

Upvotes: 1

Related Questions