How to store intermediate recursion results

Question

I would like to get the same result which is printed (using the print function in the code below) as function result. If I use a return statement in the loop, then the loop get's broken and I never get to the indexes > 0. How can I store the intermediate result in a (local) variable and eventually return as function result?

l = list("ABCD")

def remel(l, pos):
    res = l[:]
    del res[pos]
    return(res)

def f(l):
    if len(l) == 1:
        res = l
        return(res)
    else:
        for i in range(len(l)):
            res = [l[i]] + f(remel(l, i))
            print(res) # store this and pass on how?
        return(res)

f(l)

score 2 · Accepted Answer · answered Mar 04 '20 at 13:55

You can use Tail recursion for accessing intermediate recursion results. From an example given in that discussion, say you're computing a sum of first n numbers:

function tailrecsum(x, running_total = 0) {
    if (x === 0) {
        return running_total;
    } else {
        return tailrecsum(x - 1, running_total + x);
    }
}

here, the running_total is being passed to each of the calls so you can have access to the intermediate recursion calls by accessing this variable:

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
# Returns 15

score 1 · Answer 2 · answered Mar 04 '20 at 13:25

return keyword immediately stops the execution of a function and jumps back to continue execution from where the function was called. That being said, if you just want to store the values of res it can be done by replacing the last two lines of the function with the following code -

list_where_you_want_to_store.append(res) # Declare the list first, then keep appending res.
    return(list_where_you_want_to_store)

Then going forward, you can use the values stored in list where ever you want.

score 0 · Answer 3 · answered Mar 05 '20 at 07:40

Eventually solved it:

l = list("ABCD")

def remel(l, pos):
    res = l[:]
    del res[pos]
    return(res)

def f(l, mem = [], minlen = 1):
    if len(l) == minlen:
        res = l
        if res not in mem: # no duplicates
            mem.append(res)
        return(res, mem)
    else:
        for i in range(len(l)):
            res_next = f(remel(l, i), mem)
            res = [l[i]] + res_next[0]
            res.sort() # sort
            if not mem: 
                mem = [res]
            elif res not in mem: # no duplicates
                mem.append(res)
        return(res, mem)

print(f(l)[1])

#['D']
#['C', 'D']
#['C']
#['B', 'C', 'D']
#['B', 'D']
#['B']
#['B', 'C']
#['A', 'B', 'C', 'D']
#['A', 'C', 'D']
#['A', 'D']
#['A']
#['A', 'C']
#['A', 'B', 'D']
#['A', 'B']
#['A', 'B', 'C']

How to store intermediate recursion results

3 Answers3