Store output of a recursive function

Question

I wrote a recursive function to get all the possible combinations of a given list. Below is the code.

It takes a list argument and prints all possible combinations.

def getCombinations(a):
    a2 = []
    ans = ['' for i in range(len(a))]
    helper(a,ans,0)

def helper(a,ans,i):
    if i == len(ans):
        print (ans)
    else:
        ans[i] = ''
        helper(a,ans,i+1)
        ans[i] = a[i]
        helper(a,ans,i+1)

So If we call getCombinations([1,2,3]), it prints as below:

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

My question is how do I store the above result in a list. I have tried to look for solution, and I know the issue is function doesn't technically return anything, but even if I try replacing return with print(...) it doesn't work as expected and returns nothing.

You have to return on every code path - both ans and every invocation of helper. — MisterMiyagi, Sep 05 '19 at 05:19
Possible duplicate of [Why does my recursive python function return None?](https://stackoverflow.com/questions/17778372/why-does-my-recursive-python-function-return-none) — MisterMiyagi, Sep 05 '19 at 05:19
It's not exactly duplicate, moreover I actually tried returning both ans and function calls, it didn't help — Kavan Patel, Sep 05 '19 at 05:27

score 2 · Accepted Answer · answered Sep 05 '19 at 05:25

There's many ways to do this, but starting from your code, it's probably easiest to turn your function into a generator.

A generator doesn't return the whole result in one go, but each element as it becomes available. That way, you can replace your print with a yield and collect everything in a single list by wrapping the call to helper(a,ans,0) in a list().

However, since your code modifies the existing answer, you need to collect copies of the list, not the list itself, since that will change in later iterations.

So:

from copy import copy

def getCombinations(a):
    ans = ['' for i in range(len(a))]
    return list(helper(a,ans,0))

def helper(a,ans,i):
    if i == len(ans):
        yield copy(ans)
    else:
        ans[i] = ''
        yield from helper(a,ans,i+1)
        ans[i] = a[i]
        yield from helper(a,ans,i+1)

print(getCombinations([1,2,3]))

It's a very complicated way to do this though and very messy with the empty strings - why not use the standard libraries:

from itertools import combinations
print([c for n in range(4) for c in combinations([1, 2, 3], n)])

Or, more generically, for any list:

from itertools import combinations
def all_combinations(a):
    return([c for n in range(len(a)+1) for c in combinations(a, n)])
print(all_combinations([1, 2, 3]))

Thank you for your help! It looks like generators are a way to go, my goal is not to get combinations, but I am using a function that looks kind of like this, but for simplicity and posting it on here I edited for easier understanding of the problem — Kavan Patel, Sep 05 '19 at 05:31

score 0 · Answer 2 · answered Sep 05 '19 at 05:36

You can use a function that extracts the first item from the given list and concatenate it with each of the combinations returned by a recursive call with the rest of the list, until the list becomes empty:

def getCombinations(lst):
    if lst:
        first, *rest = lst
        for value in '', first:
            for combination in getCombinations(rest):
                yield [value, *combination]
    else:
        yield []

so that list(getCombinations([1, 2, 3])) returns:

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

Store output of a recursive function

2 Answers2