CODEWITHSUNDEEP
pythonrecursionbrackets
TheFoxx
TheFoxx

Reputation: 1693

Why is my python function returning multiple brackets?

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?

Upvotes: 0

Views: 819

Answers (4)

Sean Vieira
Sean Vieira

Reputation: 160025

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.

Upvotes: 5

mipadi
mipadi

Reputation: 411002

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)

Upvotes: 3

kojiro
kojiro

Reputation: 77137

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)

Upvotes: 0

newtover
newtover

Reputation: 32094

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

but you might get StackOverflow

Upvotes: 1

Related Questions