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

"I'm suppose to create deep copies of each list" Does that mean you are not supposed to cache the results of recursive calls? In this case, the will have very high complexity. — tobias_k
– tobias_k, Commented Nov 27, 2021 at 14:39
@tobias_k I'm not allowed that 2 different lists or indexes will point on the same list in memory — MadaBit
– MadaBit, Commented Nov 27, 2021 at 14:41
Do you consider the solution of your problem, created in C++? — Vadim Chernetsov
– Vadim Chernetsov, Commented Nov 27, 2021 at 14:52
@MadaBit why did you roll back your code attempt? The question would be off-topic without it. — ggorlen
– ggorlen, Commented Nov 27, 2021 at 15:25

Sayandip Dutta · Accepted Answer · 2021-11-28 05:23:19Z

4

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.

edited Nov 28, 2021 at 5:23

answered Nov 27, 2021 at 14:56

Sayandip Dutta

15.9k4 gold badges27 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

MadaBit Over a year ago

That's a great solution. Thank you very much. Is it possible with append method instead of +? Maybe with an helper function

Sayandip Dutta Over a year ago

Added a solution with append.

Stef Over a year ago

Using functools.cache defeats the whole purpose of making two recursive calls instead of one. Consider: l = recursive_list(4); print(l); [[], [[]], [[], [[]]], [[], [[]], [[], [[]]]]]; l[1].append('oops'); print(l); [[], [[], 'oops'], [[], [[], 'oops']], [[], [[], 'oops'], [[], [[], 'oops']]]]

Sayandip Dutta Over a year ago

@Stef fair. I just made sure the lists are not self-contained. I did not consider whether OP planned to append to the lists in-between, which is my oversight. Considering OP can't use slicing, or copy, or loops, not sure if the results can be cached at all. Even with some custom cache function, there needs to be some mechanism to copy the lists.

tobias_k · Accepted Answer · 2021-11-28 09:57:24Z

4

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.

edited Nov 28, 2021 at 9:57

answered Nov 27, 2021 at 14:42

tobias_k

83.1k12 gold badges130 silver badges186 bronze badges

2 Comments

MadaBit Over a year ago

Sorry. Forgot to mention that i can't use loops

no comment Over a year ago

@MadaBit return [*map(f, range(n))] then?

Ajax1234 · Accepted Answer · 2021-11-27 16:16:33Z

1

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:

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

answered Nov 27, 2021 at 16:16

Ajax1234

71.7k9 gold badges67 silver badges110 bronze badges

Comments

no comment · Accepted Answer · 2021-11-27 21:46:20Z

1

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:

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

answered Nov 27, 2021 at 21:46

no comment

10.9k5 gold badges21 silver badges44 bronze badges

4 Comments

tobias_k Over a year ago

Neat idea, but scary implementation. Why not just for _ in range(n): a.append(list(a)) and then return a?

no comment Over a year ago

@tobias_k Because of the question's "I'm not allowed to use list slicing or loops".

no comment Over a year ago

@tobias_k And also because of its "I'm not allowed to let 2 different lists or indexes point to the same list in memory".

no comment Over a year ago

@tobias_k It doesn't

Collectives™ on Stack Overflow

Creating a nested recursive list without slicing

4 Answers 4

EDIT

4 Comments

2 Comments

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

EDIT

4 Comments

2 Comments

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related