Why is my python function returning multiple brackets?

Question

I'm somewhat of a noob to python but I'm trying to create a recursive function which works just like the built in range function:

def Range (lo, hi):
    if lo >= hi:
        return []
    else:
        return [lo, Range (lo+1,hi)]

but its returning multiple lists.

Instead of [3,4,5,6], which is what I want, its returning [3,[4,[5,[6,[]]]]] Why is this and how do I fix it?

Sean Vieira · Accepted Answer · 2011-11-15T20:21:38.560

5

When you recurse like that, Range returns a list each time:

Range(3,7)
# translates to
[3, Range(4,7)]
# which translates to
[3, [4, Range(5,7)]]
# etc.

In order to avoid this, add your lists together:

def Range (lo, hi):
    if lo >= hi:
        return []
    else:
        return [lo] + Range(lo+1, hi)

EDIT:

As @delnan points out, this function is very inefficient - it both recurses in a language without tail-call optimization^* and it generates two (possibly three) new lists for each level of recursion. @mipadi's answer is more performant because it creates only one list (the acc or accumulator argument) and passes it as it recurses.

^{* This may not be true for the Python language, but I'm 99% sure it is true for the most common implementation of Python, namely CPython.}

edited Nov 15 '11 at 20:21

answered Nov 15 '11 at 18:54

Sean Vieira

155,703
32
311
293

This is *extremely* inefficient though. It's a mind-boggingly stupid inefficency too. – Nov 15 '11 at 19:47
@delnan - absolutely so - I assume that this is for learning about recursion, not building production systems :-) I up-voted mipadi's answer, as I believe it is better than mine (since it makes use of an accumulator to avoid creating multiple lists). Perhaps I should add his version here too and explain why that's a better way of doing things ... – Sean Vieira Nov 15 '11 at 20:02
@delnan - updated with a note about *why* this is not a good way of doing things, thanks for the comment and let me know if I have left anything out! – Sean Vieira Nov 15 '11 at 20:31

mipadi · Answer 2 · 2011-11-15T19:52:42.880

3

Your Range function returns a list, so in your last line you are returning a list within a list. What you probably should do is maintain an accumulator and add values to that:

def Range(lo, hi, acc=None):
    if acc is None:
        acc = []
    if lo >= hi:
        return acc
    else:
        acc.append(lo)
        return Range(lo+1, hi, acc)

edited Nov 15 '11 at 19:52

answered Nov 15 '11 at 18:54

mipadi

398,885
90
523
479

Why not `Range(lo, hi, acc=[])` directly ? – log0 Nov 15 '11 at 19:16
@Ugo - because you'll wind up with repeated calls to range returning everything that came before - try it and then read http://stackoverflow.com/questions/1132941/least-astonishment-in-python-the-mutable-default-argument – Sean Vieira Nov 15 '11 at 19:23

score 1 · Answer 3 · answered Nov 15 '11 at 18:54

1

def Range (lo, hi):
    if lo >= hi:
        return []
    else:
        return [lo] + Range (lo+1, hi)

but you might get StackOverflow

answered Nov 15 '11 at 18:54

newtover

31,286
11
84
89

Watch out for `RuntimeError: maximum recursion depth exceeded` – César Nov 15 '11 at 19:01

score 0 · Answer 4 · answered Nov 15 '11 at 18:55

Each recursion into Range returns a list, which is the second element in the list for the previous recursion. Of course Python has a built-in function for this, but if you want to build it yourself, you probably just want to end with

return [lo] + Range(lo+1, hi)

Why is my python function returning multiple brackets?

4 Answers4