Recursive Stack Calls in Python -- Mapping

Question

While working on a recursive function to generate the set of all subsets, I noticed that this fuction defined below gave me an unexpected output of:

[[]], None, None, None and None.

Why does it "work" properly when the for-loop is active, whereas it completely does not map to the desired subsets when it is not active.

print(ss)

Does not print the same thing it does when the for-loop is active.

What am I missing?

def get_all_subsets(some_list):



  """Returns all subsets of size 0 - len(some_list) for some_list"""
    if len(some_list) == 0:
        # If the list is empty, return the empty list
        return [[]]
    subsets = []

    first_elt = some_list[0]
    rest_list = some_list[1:]

    ss =  get_all_subsets(rest_list)
    print(ss)

    #    for partial_subset in ss:
    #        subsets.append(partial_subset)
    #        next_element = partial_subset[:] + [first_elt]
    #        subsets.append(next_element)
    #    return subsets


 L = [1,2,3,4]

 print(get_all_subsets(L))

What I want to see is:

[[2,3,4],[3,4],[4],[]]

Here is a more S-O worthy code:

def get_all_subsets(some_list):
    """Returns all subsets of size 0 - len(some_list) for some_list"""
    if len(some_list) == 0:
        # If the list is empty, return the empty list
        return [[]]
    subsets = []

    first_elt = some_list[0]
    rest_list = some_list[1:]

    ss =  get_all_subsets(rest_list)
    print(ss)

    for partial_subset in ss:
        print(partial_subset)
        #        subsets.append(partial_subset)
#        next_element = partial_subset[:] + [first_elt]
#        subsets.append(next_element)
    return subsets

also, see [how-can-i-find-all-the-subsets-of-a-set-with-exactly-n-elements](https://stackoverflow.com/questions/374626/how-can-i-find-all-the-subsets-of-a-set-with-exactly-n-elements) if you need the functionality w/o any "students do this, but do not use that and those and these" strings attached — Patrick Artner, Dec 17 '17 at 15:29
Indentation is off. Without a return statement a function returns `None`. — hpaulj, Dec 17 '17 at 15:30

Patrick Artner · Answer 1 · 2017-12-17T15:51:17.383

1

It does not work because you return nothing in case the list is non-empty (you just print() ). if you do not return anything explicitly the function returns None implicitly

def get_all_subsets(some_list): 
    if len(some_list) == 1: # if len is 1 then the last element was added
                            # previously, just add the empty list
        return [[]]

    if len(some_list) > 1:  # add rest of list and recurse
        return [some_list[1:]] + get_all_subsets(some_list[1:]) 


L = [1,2,3,4]
print( get_all_subsets(L))

Output:

[[2, 3, 4], [3, 4], [4], []]

edited Dec 17 '17 at 15:51

answered Dec 17 '17 at 15:33

Patrick Artner

50,409
9
43
69

Thank you: I now see when the comments are removed, we get the "return". I am still experimenting with this to better understand the stack's interaction with recursion. – Phil Dec 17 '17 at 15:56

Recursive Stack Calls in Python -- Mapping

1 Answers1