simple list recursion in python

Question

I'm trying to wrap my head around the concept of recursion and has the following queries with regard to the output of the below code:

def subsetsofSet(input_list, set_list=None):
    print "IN input_list: {0}".format(input_list)
    if not input_list:
        return

    input_list.pop()

    subsetsofSet(input_list)
    print "RETURN input_list: {0}".format(input_list)

subsetsofSet([1,2,3])

Output is as below:

IN input_list: [1, 2, 3]
IN input_list: [1, 2]
IN input_list: [1]
IN input_list: []
RETURN input_list: []
RETURN input_list: []
RETURN input_list: []

Why is the RETURN input_list always empty? Shouldn't it be displayed in the reverse manner of the IN input_list? Appreciate any help in understanding this?

could you add the expected output to be and is your indentation right ? — The6thSense
– The6thSense, Commented Nov 30, 2015 at 7:10
i was expecting the output to be as below IN input_list: [1, 2, 3] IN input_list: [1, 2] IN input_list: [1] IN input_list: [] RETURN input_list: [1] RETURN input_list: [1,2] RETURN input_list: [1,2,3] — parseltonguenewbie
– parseltonguenewbie, Commented Nov 30, 2015 at 7:14
@thefourtheye That would be true if they were actually using the return value of the function anywhere; it doesn't look like they are. — user1726343
– user1726343, Commented Nov 30, 2015 at 7:20
@OP The RETURN input_list is always empty because you recursively pop all elements from the list before any of the function calls end. — user1726343
– user1726343, Commented Nov 30, 2015 at 7:20

Serge Ballesta · Accepted Answer · 2015-11-30 08:23:25Z

1

A list is a mutable element, so you only pass a reference to the original list and it is popped on each call. If you printed the id of the list, you could see the same value.

So even if before calling subsetsofSet(input_list) for the second time the list was [1,2] after the return it is empty.

You should pass a copy of the list if you do not want it to be changed by recursive calls:

def subsetsofSet(input_list, set_list=None):
    print "IN input_list: {0}".format(input_list)
    if not input_list:
        return

    input_list.pop()

    subsetsofSet(input_list[:])
    print "RETURN input_list: {0}".format(input_list)

subsetsofSet([1,2,3])

Output is then:

IN input_list: [1, 2, 3]
IN input_list: [1, 2]
IN input_list: [1]
IN input_list: []
RETURN input_list: []
RETURN input_list: [1]
RETURN input_list: [1, 2]

answered Nov 30, 2015 at 8:23

Serge Ballesta

150k13 gold badges137 silver badges267 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

simple list recursion in python

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related