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 — ggorlen
– ggorlen, Commented Dec 10, 2022 at 20:23
@ggorlen Thanks! but I am not allowed to import copy, which make it harder to solve — Dr.jj
– Dr.jj, Commented Dec 10, 2022 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
– ggorlen, Commented Dec 10, 2022 at 23:10

Timmy Diehl · Accepted Answer · 2022-12-11 01:36:42Z

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, 2022 at 1:36

Timmy Diehl

3095 silver badges19 bronze badges

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

1 Comment

DonLarry Over a year ago

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)

chepner · Accepted Answer · 2022-12-11 02:00:53Z

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.

Collectives™ on Stack Overflow

Recursive function to nested lists

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related