create a recursive list without slicing-CodePudding

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 suppose to create deep copies of each list, without the copy module, I'm not allowed that 2 different lists or indexes will point on 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 [[], [...]]

CodePudding user response：

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)]

It is recommended to use caching. A cached version would be (using functools.cache)

from functools import cache
@cache
def recursive_list(n: int) -> list:
    if n:
        return recursive_list(n-1)    [recursive_list(n-1)]
    return []

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 []

But if you plan to cache the results, the approach needs to be a little different. Although it is possible to do this using list.append instead of __add__, the problem is append modifies the list inplace, which can lead to some unintended results. In order to avoid that, you will need to slice intermediate results every time, to ensure copy of the lists, and not views.

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

CodePudding user response：

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)]

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

CodePudding user response：

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:

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