Creating a nested recursive list without slicing

Question

I need to write a function that receives an non-negative integer and returns:

[] for n=0 

[[]] for n=1 

[[],[[]]] for n=2

[[],[[]],[[],[[]]]] for n=3

And so on. For n, we will receive an n sized list, so that in index i there will be all the i-1 elements from the list. I don't know how to explain that better, English isn't my first language.

I'm not allowed to use list slicing or loops and I'm supposed to create deep copies of each list, without the copy module. I'm not allowed to let 2 different lists or indexes point to the same list in memory.

This is what I tried:

def list_seq(x, outer_list=[]):
    if x == 0:
        return []
    outer_list.append(list_seq(x-1,outer_list))
    return outer_list

And the output for print(list_seq(2)) is [[], [...]].

Answer 1

If you can't use loops, you can use the following:

def recursive_list(n):
    if n == 0:
        return []
    else:
        return recursive_list(n-1) +  [recursive_list(n-1)]

EDIT

You can do the following if you want to use append:

def recursive_list(n: int) -> list:
    if n:
        result = recursive_list(n-1)
        result.append(recursive_list(n-1))
        return result
    return []

NOTE as pointed out in the comments, caching introduces some reference issues, so I have removed the cached versions.

Answer 2

You can write this down as a recursive function using a simple list comprehension:

def f(n):
    return [f(i) for i in range(n)]

Or instead of the list comprehension, you could also use map:

def f(n):
    return list(map(f, range(n)))

Note, though, that without caching this is going to get rather slow rather quickly.

Answer 3

An alternative shorter recursive solution, no loops:

def l_list(n):
  def f(c, d = []):
     return d if c == n else f(c+1, d+[l_list(c)])
  return f(0)

print(l_list(0))
print(l_list(1))
print(l_list(2))
print(l_list(3))

Output:

[]
[[]]
[[], [[]]]
[[], [[]], [[], [[]]]]

Answer 4

Just another idea, I think it fulfills all rules/requirements:

def f(n):
    a = []
    exec('a.append(1 * a);' * n)
    return eval(repr(a))

Demo usage:

for n in range(5):
    print(f(n))

Output:

[]
[[]]
[[], [[]]]
[[], [[]], [[], [[]]]]
[[], [[]], [[], [[]]], [[], [[]], [[], [[]]]]]