CODEWITHSUNDEEP
pythonrecursion
mdvenkatesh nuhk
mdvenkatesh nuhk

Reputation: 125

how the return is working in recursion with reference to the following code

def subs(l):
    if l == []:
        return [[]]

    x = subs(l[1:])

    return x + [[l[0]] + y for y in x]

1) I am trying to understand working of the above code

2) If l = [1,2,3] at the end of the recursion we will get an empty list of list

3) In last next iteration we will be given the result to the x will be 3 (I am thinking it will go to the next step which is return)

4) In these returns I am thinking it will add return x + [[l[0]] + y for y in x] should return (3,3).

5) By ending of these step the answer should be (3,3).

The final answer according to be at the second step must be [[],[3,3]].

But the code is printing a different answer.

o/p 

[], [3]]

Can any one explain where my assumption went wrong and how return x + [[l[0]] + y for y in x] these steps are working?

Upvotes: 0

Views: 56

Answers (1)

user10325516
user10325516

Reputation:

I made some modifications to the code to make it print intermediate results:

def subs(l, num=0):

    print(' ' * num, 'current l is:', l)
    print()

    if l == []:
        return [[]]

    x = subs(l[1:], num + 4)
    print(' ' * num, 'current x is:', x)

    answer = x + [[l[0]] + y for y in x]
    print(' ' * num, 'current answer is:', answer)

    print()

    return answer

subs([1, 2, 3])

Let's have a look at the output (it's an image):

enter image description here

Indentation depictures resursion depth. Black arrows show calculation flow. Red arrows show which l and x correspond to each other (belong to the same namespace). From the image one can see how recursion differs from loops. Recursion goes all the way down to the trivial case and then goes up. Pay attention to the red arrows.

So, first, x is never 3. It just can't be actually. Second, l can be [3]. Corresponding x is [[]] returned by the final recursion step (trivial case). These values give you answer [[], [3]]. And this is x for the previous l = [2, 3].

Upvotes: 1

Related Questions