How do I implement this piece of python code using recursion?

Question

I'm trying to find a recursive way to do this by passing the number of for loops in a recursive function:

def non_recursive():
  combinations = []

  for i in range(2): # first character
    for j in range(2): # second character
      for k in range(2): # third character
        combinations.append([i, j, k])

  return combinations

print(non_recursive())

Output:

[[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

In this example 3 for loops were used. The function prototype for the recursive way should look like this:

def recursive(number_of_iterations): # number of iterations = length of each list
  # implementation goes here!

As a beginner, I have no idea how to approach this. If anyone can help I really appreciate it!

Answer 1

You have to combine each result from recursive(n-1) with [0] and with [1]:

Here's an example using a two level list comprehension:

def recursive(n):
    if n == 1: return [[0],[1]]
    return [ r+[b] for r in recursive(n-1) for b in [0,1] ]


print(recursive(3))

# [[0, 0, 0], [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 0, 1], [1, 1, 0], [1, 1, 1]]

These type of combinatoric functions however are usually defined as generators so that results can be processed without having to generate and store all the values in a big list:

def recursive(n):
    if n == 1:
        yield [0]
        yield [1]
    else:
        for r in recursive(n-1):
            yield r+[0]
            yield r+[1]

for combo in recursive(3): print(combo)

[EDIT] you can generalize this further by providing (variable) range sizes as parameters:

def multiRange(n,*rest):
    for i in range(n):
        for r in multiRange(*rest) if rest else [tuple()]:
            yield (i,)+r

output:

for x,y,z in multiRange(2,3,2):
    print((x,y,z))

(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(0, 2, 0)
(0, 2, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)
(1, 2, 0)
(1, 2, 1)

this would be useful to get all the coordinates of a multi-dimentional matrix (or list of lists)

It could be used with parameter unpacking for your specific example:

for combo in multiRange(*[2]*3): print(combo)

(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(0, 1, 1)
(1, 0, 0)
(1, 0, 1)
(1, 1, 0)
(1, 1, 1)