Recursive function to nested lists

Question

I have tried to crate a recursive function that gets a number and returns a list of nested list according to the index. For example, for 0, the function returns an empty list []. for 1, the function returns [[], [[]]]. for 3 the function returns [ [] , [ [] ] , [ [] , [ [] ] ]], and so on.

def func(n):
    if n == 0:
        return []
    return [func(n-1)]

i have tried many different approaches for this problem. I cant figure out how to extend my output to nested list according to the task.

Very close question to [How do i make a recursive function in python which does the following? magic list](https://stackoverflow.com/questions/72186151/how-do-i-make-a-recursive-function-in-python-which-does-the-following-magic-lis) — ggorlen, Dec 10 '22 at 20:23
@ggorlen Thanks! but I am not allowed to import copy, which make it harder to solve — Dr.jj, Dec 10 '22 at 22:39
Did you look at all of the answers at that link? It's not quite the same, because of your seemingly odd `n=0` expected result, but other than that, it's more or less the same, so you should be able to adapt techniques there to solve this. — ggorlen, Dec 10 '22 at 23:10
Also related: [Sequence of nested lists recursive python](https://stackoverflow.com/questions/74777281/sequence-of-nested-lists-recursive-python) — ggorlen, Dec 12 '22 at 22:13

score 1 · Answer 1 · answered Dec 11 '22 at 01:36

1

What I think you're looking for is something like this:

def f(n):
    L = []
    for i in range(n):
        L.append(f(i))
    return L

My confusion stems from your examples. For n=0, there are 0 elements and for n=3 there are 3 elements, but there are 2 elements for n=1. This should work where n is the number of elements in the final list

answered Dec 11 '22 at 01:36

Timmy Diehl

409
3
16

I think this answer is correct and does what the asker is apparently trying to do, but just as a suggestion to the asker, I would also add memoization to it to avoid a lot of unnecessary computation (if you want, I can edit and add behind a version with memoization) – DonLarry Dec 11 '22 at 04:05

chepner · Answer 2 · 2022-12-11T02:00:53.833

Each list actually contains all the preceding lists, not just the immediately preceding list. (Based on your example for func(3), your question seems to mistakenly refer to the list returned by func(2) as the list returned by func(1).)

func(0) == []
func(1) == [func(0)] == [[]]
func(2) == [func(0), func(1)] == [[], [[]]]
func(3) == [func(0), func(1), func(2)] == [[] , [[]] , [[], [[]]]]
...
func(n) == [func(0), func(1), ..., func(n-1)]

This is basically a set-theoretic definition of the natural numbers, due to von Neumann. Zero is define to be the empty set, and the successor of each number x is the union of x and the set containing x:

0 == {}
1 == 0 | {0} == {} | {{}} == {{}}
2 == 1 | {1} == {{}} | {{{}}} == {{}, {{}}}

I leave it as an exercise to implement this using lists instead of sets.

Recursive function to nested lists

2 Answers2

Linked