Problems with recursion

Question

Given:

numma = [1,2,3,4], n = 7

I expected the following code to return:

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

Instead, it returns a list with four copies of:

[1,2,4]

and six copies of:

[1,2,3,4]

The script is intended to take the elements of the list numbers = numma in order, and form a new list (this_chain) with them, as long as the sum of the elements in this_chain does not exceed n = 7.

When adding a new element would break that condition, the list this_chain is appended to another list (all_chains), and the process begins again. If the original list (numbers) runs out of elements, the current this_chain is appended to all_chains and the script finishes, returning the list (of lists) called all_chains.

When I run it step by step, it follows the expected behavior, but upon reaching the return statement (step 84), instead of returning all_chains and finish, the arrow moves half a step downwards and then jumps back to the first statement (for i in ...). Then it goes back down and appends another copy of the current this_chain to all_chains, and so on, taking 66 additional steps and returning the output I mentioned above.

It was suggested to me to iterate over a tuple, instead of over a list, but since I want to remove elements from the iteration sequence I do not see how it could be done.

I am pretty puzzled. The four questions I'd like to ask, in order of importance, are the following:

1. Why does the program not finish upon reaching the return statement? I believed a return statement would always terminate any script.

2. Given the behavior described above, why does the script finally end, instead of keeping on appending copies of valid lists to the list called all_chains?

3. Why does the script append invalid elements to the list all_chains, that is, lists whose elements sum up more than n = 7?

4. Why are elements already in all_chains removed (or modified), so that they are not present in the final output, even if they were appended to the list all_chains previously?

My code:

def chain(numbers, n, all_chains=[], sum=0, this_chain=[]):
  for i in range(len(numbers)):
    if numbers[i] not in this_chain:
        sum += numbers[i]
        if sum <= n:
            this_chain.append(numbers[i])
            chain(numbers, n, all_chains, sum, this_chain)
        else:
            if this_chain not in all_chains:
                all_chains.append(this_chain)
                mocha = numbers[:]
                mocha.remove(this_chain[-1])
                chain(mocha, n, all_chains, sum=0, this_chain=[])
  all_chains.append(this_chain)
  return all_chains
numma = [1,2,3,4]
chain(numma, 7, chains=[], sum=0, this_chain=[])

Answer 1

1. Why does the program not finish upon reaching the return statement? I believed a return statement would always terminate any script.

return does not terminate the script; it leaves the current routine and returns control to the one that called it. When you're in a recursive call, it simply returns control to the "elder" version of itself that called it.

2. Given the behavior described above, why does the script finally end, instead of keeping on appending copies of valid lists to the list called all_chains?

It ends because it all active invocations eventually make it to the bottom of the function, ending their executions.

3. Why does the script append invalid elements to the list all_chains, that is, lists whose elements sum up more than n = 7?

The problem is when you return to try adding 4, the list you think you have is [1, 2], but it actually reads [1, 2, 3] because ... well, see the next point.

4. Why are elements already in all_chains removed (or modified), so that they are not present in the final output, even if they were appended to the list all_chains previously?

Wherever you append to a list, you append a reference to the original, rather than a local copy. This comes from using mutable objects (as @tobias_k already noted). Thus, when you append [1, 2, 3] to the list (several times), all of these are the same object. When you later mistakenly append 4 to the list (thinking that the list has only [1, 2] in it), you change all the references to [1, 2, 3, 4]. I've fixed this in the code below.

Finally, you have all those extra lists because of the missing return statements; instead of stopping when you should, you go through the rest of the function, making more calls, and finding more copies of the same solutions.

I've added some stuff to your code so you can watch the execution. Most of all, I've added some ugly, but useful, print statements to track the execution. I have modules to handle the indentation, counts, and argument printing in more readable form, you can experiment to see what you find most readable.

I've also replaced your straight append operations with copies, so you can differentiate the problems better and learn more from your mistakes.

Remember, good choices come from experience. Experience comes from bad choices.

import copy

invocation = 0

def chain(numbers, n, all_chains=[], sum=0, this_chain=[]):
    global invocation
    invocation += 1
    local_id = invocation
    indent = "  "

    print indent*local_id, local_id, "ENTER", "\tsum", sum, "\tthis", this_chain, "\tall", all_chains
    for i in range(len(numbers)):
        if numbers[i] not in this_chain:
            sum += numbers[i]
            if sum <= n:
                print indent*local_id, local_id, "append to this", sum, this_chain, numbers[i]
                this_chain.append(numbers[i])
                chain(numbers, n, all_chains, sum, this_chain)
            else:
                if this_chain not in all_chains:
                    print indent*local_id, local_id, "append to all 1", this_chain
                    all_chains.append(copy.copy(this_chain))
                    mocha = numbers[:]
                    mocha.remove(this_chain[-1])
                    chain(mocha, n, all_chains, sum=0, this_chain=[])
    print indent*local_id, local_id, "append to all 2", this_chain
    all_chains.append(copy.copy(this_chain))
    print indent*local_id, local_id, "LEAVE", all_chains
    return all_chains

numma = [1, 2, 3, 4]
result = chain(numma, 7)
print
for x in result:
    print x

Execution trace:

   1 ENTER  sum 0   this []     all []
   1 append to this 1 [] 1
     2 ENTER    sum 1   this [1]    all []
     2 append to this 3 [1] 2
       3 ENTER  sum 3   this [1, 2]     all []
       3 append to this 6 [1, 2] 3
         4 ENTER    sum 6   this [1, 2, 3]  all []
         4 append to all 1 [1, 2, 3]
           5 ENTER  sum 0   this []     all [[1, 2, 3]]
           5 append to this 1 [] 1
             6 ENTER    sum 1   this [1]    all [[1, 2, 3]]
             6 append to this 3 [1] 2
               7 ENTER  sum 3   this [1, 2]     all [[1, 2, 3]]
               7 append to this 7 [1, 2] 4
                 8 ENTER    sum 7   this [1, 2, 4]  all [[1, 2, 3]]
                 8 append to all 2 [1, 2, 4]
                 8 LEAVE [[1, 2, 3], [1, 2, 4]]
               7 append to all 2 [1, 2, 4]
               7 LEAVE [[1, 2, 3], [1, 2, 4], [1, 2, 4]]
             6 append to all 2 [1, 2, 4]
             6 LEAVE [[1, 2, 3], [1, 2, 4], [1, 2, 4], [1, 2, 4]]
           5 append to all 2 [1, 2, 4]
           5 LEAVE [[1, 2, 3], [1, 2, 4], [1, 2, 4], [1, 2, 4], [1, 2, 4]]
         4 append to all 2 [1, 2, 3]
         4 LEAVE [[1, 2, 3], [1, 2, 4], [1, 2, 4], [1, 2, 4], [1, 2, 4], [1, 2, 3]]
       3 append to all 2 [1, 2, 3]
       3 LEAVE [[1, 2, 3], [1, 2, 4], [1, 2, 4], [1, 2, 4], [1, 2, 4], [1, 2, 3], [1, 2, 3]]
     2 append to this 7 [1, 2, 3] 4
                   9 ENTER  sum 7   this [1, 2, 3, 4]   all [[1, 2, 3], [1, 2, 4], [1, 2, 4], [1, 2, 4], [1, 2, 4], [1, 2, 3], [1, 2, 3]]
                   9 append to all 2 [1, 2, 3, 4]
                   9 LEAVE [[1, 2, 3], [1, 2, 4], [1, 2, 4], [1, 2, 4], [1, 2, 4], [1, 2, 3], [1, 2, 3], [1, 2, 3, 4]]
     2 append to all 2 [1, 2, 3, 4]
     2 LEAVE [[1, 2, 3], [1, 2, 4], [1, 2, 4], [1, 2, 4], [1, 2, 4], [1, 2, 3], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4]]
   1 append to all 2 [1, 2, 3, 4]
   1 LEAVE [[1, 2, 3], [1, 2, 4], [1, 2, 4], [1, 2, 4], [1, 2, 4], [1, 2, 3], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]]

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