I need to append a deep copy (not a reference) of list to itslef recursively n times, for example for

n=0 -> []
n = 1 -> [[]]
n=2 -> [[], [[]]] 
and so forth. 

this is what I wrote so far:

def magic_list(n: int) -> List[Any]:
    #take only positive numbers
    assert(n>=0)
    
    if n == 0:
        return []
    else:
        return magic_list_helper(0, n, [])

the main function, I have to keep this def signature exactly the same(takes only n:int). this is the helper function I wrote:

def magic_list_helper(index: int,threshold:int ,lst:List[Any]) -> List[Any]:
    if index >= threshold:
        return lst
    
    else:
        
        # temp_lst = deepcopy(lst)
        # lst.append(temp_lst)
        return magic_list_helper(index   1, threshold, lst)

for this problem I cannot use copy.deepcopy or any other external libraries(thats why its with #, without it it works) and I could not find a solution online without deep copy. Also I cannot use List comprehension, slicing or any O(n) operations on lists(I can use append). Hope you can help me, thanks in advance.

CodePudding user response：

You can try this. Not sure if it's the correct one.

l=[]
n=2
for i in range(n):
    l.append(l.copy())
print(l)

CodePudding user response：

You don't need to make copies. Each call can use a list comprehension that executes n times, calling itself recursively. The list comprehension creates new lists of the appropriate lengths.

You don't even need to check for the base case, because when n == 0 the list comprehension will return an empty list.

def magic_list(n: int) -> List[Any]:
    return [magic_list(x) for x in range(n)]

for i in range(5): print(magic_list(i))

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

CodePudding user response：

Using inductive reasoning is the foundation for recursive problem solving -

1. If n is less than or equal to zero, the work is done. Return the empty result, []
2. (inductive) n is at least 1 (positive). Find the result of the sub-problem, magic_list(n - 1) and concatenate it to the singleton list of the same sub-problem, [magic_list(n - 1)]

# write
def magic_list(n):
  if n <= 0: return []
  return magic_list(n - 1)   [magic_list(n - 1)]

Recursion is a functional heritage and so using it with functional style yields the best results. That means avoiding things like mutation (.append), variable reassignments, and other side effects.

# test
for n in range(5):
  print(magic_list(n))

# output
[]
[[]]
[[], [[]]]
[[], [[]], [[], [[]]]]
[[], [[]], [[], [[]]], [[], [[]], [[], [[]]]]]

In the above program, you can see the sub-problem magic_list(n - 1) is calculated twice. We cut the work in half by assigning the result to a variable -

# optimize
def magic_list(n):
  if n == 0: return []
  m = magic_list(n - 1) # ✏️
  return m   [m]        #