Confounding recursive list append in Python

temp = fresh_start

does not make a copy. Appending doesn't make copies, assignment doesn't make copies, and pretty much anything that doesn't say it makes a copy doesn't make a copy. If you want a copy, slice it:

fresh_start[:]

is a copy.

When I look at the desired output I can't help but think about using one of the numpy grid data production functions.

import numpy
first_column, second_column, third_column = numpy.mgrid[1:4,1:4,1:4]
numpy.dstack((first_column.flatten(),second_column.flatten(),third_column.flatten()))
Out[23]: 
array([[[1, 1, 1],
    [1, 1, 2],
    [1, 1, 3],
    [1, 2, 1],
    [1, 2, 2],
    [1, 2, 3],
    [1, 3, 1],
    [1, 3, 2],
    [1, 3, 3],
    [2, 1, 1],
    [2, 1, 2],
    [2, 1, 3],
    [2, 2, 1],
    [2, 2, 2],
    [2, 2, 3],
    [2, 3, 1],
    [2, 3, 2],
    [2, 3, 3],
    [3, 1, 1],
    [3, 1, 2],
    [3, 1, 3],
    [3, 2, 1],
    [3, 2, 2],
    [3, 2, 3],
    [3, 3, 1],
    [3, 3, 2],
    [3, 3, 3]]])

Of course, the utility of this particular approach might depend on the variety of input you need to deal with, but I suspect this could be an interesting way to build the data and numpy is pretty fast for this kind of thing. Presumably if your input list has more elements you could have more min:max arguments fed into mgrid[] and then unpack / stack in a similar fashion.

Here is a simplified version of your program, which works. Comments will follow.

number_list = []

def _adjust_counter_value(counter, n, max_count):
    """
    We want the counter to go from 1 to max_count, then start over at 1.
    This function adds n to the counter and then returns a tuple:
    (new_counter_value, carry_to_next_counter)
    """
    assert max_count >= 1
    assert 1 <= counter <= max_count

    # Counter is in closed range: [1, max_count]
    # Subtract 1 so expected value is in closed range [0, max_count - 1]
    x = counter - 1 + n
    carry, x = divmod(x, max_count)

    # Add 1 so expected value is in closed range [1, max_count]
    counter = x + 1
    return (counter, carry)

def increment_counter(start, i, max_count):
    last = len(start) - 1 - i
    copy = start[:]  # make a copy of the start

    add = 1  # start by adding 1 to index
    for i_cur in range(last, -1, -1):
        copy[i_cur], add = _adjust_counter_value(copy[i_cur], add, max_count)
        if 0 == add:
            return (copy, i, max_count)
    else:
        # if we have a carry out of the 0th position, we are done with the sequence
        return None

def all_values(fresh_start, i, max_count):
    number_list.append(fresh_start)
    new_values = increment_counter(fresh_start,i,max_count)
    if new_values != None:
        all_values(*new_values)

all_values([1,1,1],0,3)

import itertools as it
correct = [list(tup) for tup in it.product(range(1,4), range(1,4), range(1,4))]
assert number_list == correct

Since you want the counters to go from 1 through max_count inclusive, it's a little bit tricky to update each counter. Your original solution was to use several if statements, but here I have made a helper function that uses divmod() to compute each new digit. This lets us add any increment to any digit and will find the correct carry out of the digit.

Your original program never changed the value of i so my revised one doesn't either. You could simplify the program further by getting rid of i and just having increment_counter() always go to the last position.

If you run a for loop to the end without calling break or return, the else: case will then run if there is one present. Here I added an else: case to handle a carry out of the 0th place in the list. If there is a carry out of the 0th place, that means we have reached the end of the counter sequence. In this case we return None.

Your original program is kind of tricky. It has two explicit return statements in counter() and an implicit return at the end of the sequence. It does return None to signal that the recursion can stop, but the way it does it is too tricky for my taste. I recommend using an explicit return None as I showed.

Note that Python has a module itertools that includes a way to generate a counter series like this. I used it to check that the result is correct.

I'm sure you are writing this to learn about recursion, but be advised that Python isn't the best language for recursive solutions like this one. Python has a relatively shallow recursion stack, and does not automatically turn tail recursion into an iterative loop, so this could cause a stack overflow inside Python if your recursive calls nest enough times. The best solution in Python would be to use itertools.product() as I did to just directly generate the desired counter sequence.

Since your generated sequence is a list of lists, and itertools.product() produces tuples, I used a list comprehension to convert each tuple into a list, so the end result is a list of lists, and we can simply use the Python == operator to compare them.