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, Nov 30 '15 at 07: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, Nov 30 '15 at 07: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. — Asad Saeeduddin, Nov 30 '15 at 07: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. — Asad Saeeduddin, Nov 30 '15 at 07:20
@parseltonguenewbie You are removing from the last element but why is that you are adding from the first element can you justify your output — The6thSense, Nov 30 '15 at 07:22
@AsadSaeeduddin I do understand that I'm popping the elements of the list. But when the recursive call returns shouldn't it be returning the value of input_list in the particular stack frame for the `RETURN input_list`? — parseltonguenewbie, Nov 30 '15 at 08:03
Python `list`s are objects, which means they are passed "by reference" in function parameters. `input_list` refers to the same object across all stack frames, because of this. — , Nov 30 '15 at 08:18

score 1 · Accepted Answer · answered Nov 30 '15 at 08:23

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]

simple list recursion in python

1 Answers1