List of lists using recursion

Question

I've been stuck for a while on some online learning I've been trying.

I need to create a list of empty lists using recursion.

The strange thing is that I thought that I understood a factorial algorithm (which there is lots of help for) but not with this and as a result it always just returns the single [ ].

For example if n=4 then I would expect [[ ], [ ], [ ] ,[ ]]

def listOfLists(n):

    lists = []

        if i <= 1:
            return lists
        else:
            lists += lists.append([])
            listOfLists(n-1)

This is where I've got myself into a twist. On this particular attempt I tried starting with the for but on my other attempts it just started with if statements. — Bob24
– Bob24, Commented Mar 14, 2019 at 13:46
Thanks BoarGules but I have to use recursion in this particular method. — Bob24
– Bob24, Commented Mar 14, 2019 at 13:51
I nearly didn't post as I've heard lots of negative things about the responses on SO. So before I posted I read this and set me at ease. stackoverflow.blog/2018/04/26/… — Bob24
– Bob24, Commented Mar 14, 2019 at 14:37
SO can certainly be welcoming, all we ask is that users put a certain amount of effort into solving the problem on their own before coming here, additionally providing all the information needed in the question itself, including code, the problem encountered, what you've tried, what you're trying to do, what results you expect, what results you get instead, etc. If you're interested I suggest you read Jon Skeet's blog post about writing the perfect question (It's quite a read but has some interesting points in it) — Nick is tired
– Nick is tired, Commented Mar 14, 2019 at 15:02

Nick is tired · Accepted Answer · 2019-03-14 13:57:29Z

4

You don't use the response of your recursive call, try to understand this code (I've tried to keep the form similar to yours):

def listOfLists(n):
    lists = [[]]
    if n <= 1:
        return lists
    else:
        return lists + listOfLists(n-1)

This written "dry-run" may help you understand it (for listOfLists(3)):

Call - listOfLists(3)
 Call - listOfLists(2)
  Call - listOfLists(1)
  Return [[]] # From listOfLists(1)
 Return [[]] + [[]] # From listOfLists(2)
Return [[]] + [[],[]] # From listOfLists(3)

answered Mar 14, 2019 at 13:57

Nick is tired

7,17721 gold badges44 silver badges55 bronze badges

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

1 Comment

Bob24 Over a year ago

Thank you. This works a treat, I'm now going to go through all my previous versions to determine where I was going so wrong.

Daweo · Accepted Answer · 2019-03-14 14:08:52Z

1

Recursive function was already given in others answer, I want to explain why your code do not work as expected. Culprit is that line:

lists += lists.append([])

instead it should be:

lists.append([])

or alternatively:

lists = lists+[[]]

Note that .append method add element at end of list and returns None, consider following example:

x = [1,2,3]
y = x.append(4)
print(y) #None
print(x) #[1, 2, 3, 4]

As you might see append method altered x list and y is None, not [1,2,3,4]. Nonetheless your function, even after described repair would not be recursive function.

edited Mar 14, 2019 at 14:08

answered Mar 14, 2019 at 14:01

Daweo

38.2k3 gold badges17 silver badges32 bronze badges

Comments

pjs · Accepted Answer · 2019-03-14 14:00:37Z

0

Another variant for your consideration. This uses an additional argument with a default value.

def listOfLists(n, lists = []):
    if n > 0:
        lists.append([])
        return listOfLists(n-1, lists)
    else:
        return lists

print(listOfLists(4))

answered Mar 14, 2019 at 14:00

pjs

20k4 gold badges30 silver badges64 bronze badges

Comments

BoarGules · Accepted Answer · 2019-03-14 14:01:36Z

0

If you must use recursion to solve a problem better suited to repetition, you can do this. I've kept as close to your original as I reasonably could.

def listOfLists(n):
    if n <= 0:
        return []
    else:
        return [ [] ] + listOfLists(n-1)

>>> listOfLists(4)
[[], [], [], []]

answered Mar 14, 2019 at 14:01

BoarGules

17.1k3 gold badges29 silver badges46 bronze badges

Comments

ncica · Accepted Answer · 2019-03-14 14:12:22Z

0

def listOfLists(n,lists=[]):
    lists.append([])
    if n == 1:   
        return

    listOfLists(n-1,lists)
    return lists

print (listOfLists(4))

result: [[], [], [], []]

edited Mar 14, 2019 at 14:12

answered Mar 14, 2019 at 14:05

ncica

7,2161 gold badge19 silver badges41 bronze badges

Comments

Ajax1234 · Accepted Answer · 2019-03-14 14:24:55Z

0

There are great recursive answers posted, however, it is also possible to use generators with recursion:

def listOfLists(n):
   if n:
     yield []
     yield from listOfLists(n-1)

print(list(listOfLists(4)))

Output:

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

answered Mar 14, 2019 at 14:24

Ajax1234

71.7k9 gold badges67 silver badges110 bronze badges

1 Comment

Bob24 Over a year ago

Thank you but I haven't got to something like this yet but no doubt it will be useful.

Maxouille · Accepted Answer · 2019-03-14 14:01:36Z

-1

You can do this :

def listoflist_func(n, currentList=[]):
    if n < 0:
        return "Error: n must be > 0"
    elif n==0:
        return currentList
    else:
        currentList.append([])
        return listoflist_func(n-1, currentList)


print listoflist_func(4)

Result is :

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

Best

edited Mar 14, 2019 at 14:01

answered Mar 14, 2019 at 13:50

Maxouille

2,9112 gold badges22 silver badges43 bronze badges

2 Comments

Bob24 Over a year ago

Thanks Macouille but I have to use recursion in this particular method.

Maxouille Over a year ago

Updated my answer, srry

Collectives™ on Stack Overflow

List of lists using recursion

7 Answers 7

1 Comment

Comments

Comments

Comments

Comments

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

7 Answers 7

1 Comment

Comments

Comments

Comments

Comments

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related