CODEWITHSUNDEEP
pythonlistrecursion
Malyk
Malyk

Reputation: 193

Get length of list in Python using recursion

I am trying to calculate the length of a list. When I run it on cmd, I get:

RuntimeError: maximum recursion depth exceeded in comparison

I don't think there's anything wrong with my code:

def len_recursive(list):
    if list == []:
        return 0
    else:
        return 1 + len_recursive(list[1:])

Upvotes: 3

Views: 7202

Answers (6)

zch
zch

Reputation: 15278

Don't use recursion unless you can predict that it is not too deep. Python has quite small limit on recursion depth.

If you insist on recursion, the efficient way is:

def len_recursive(lst):
    if not lst:
        return 0
    return 1 + len_recursive(lst[1::2]) + len_recursive(lst[2::2])

Upvotes: 3

poke
poke

Reputation: 388023

Your exception message means that your method is called recursively too often, so it’s likely that your list is just too long to count the elements recursively like that. You could do it simply using a iterative solution though:

def len_iterative(lst):
    length = 0
    while lst:
        length += 1
        lst = lst[1:]
    return length

Note that this will very likely still be a terrible solution as lst[1:] will keep creating copies of the list. So you will end up with len(lst) + 1 list instances (with lengths 0 to len(lst)). It is probably the best idea to just use the built-in len directly, but I guess it was an assignment.

Upvotes: 1

Óscar López
Óscar López

Reputation: 236114

The recursion depth in Python is limited, but can be increased as shown in this post. If Python had support for the tail call optimization, this solution would work for arbitrary-length lists:

def len_recursive(lst):
    def loop(lst, acc):
        if not lst:
            return acc
        return loop(lst[1:], acc + 1)
    return loop(lst, 0)

But as it is, you will have to use shorter lists and/or increase the maximum recursion depth allowed.

Of course, no one would use this implementation in real life (instead using the len() built-in function), I'm guessing this is an academic example of recursion, but even so the best approach here would be to use iteration, as shown in @poke's answer.

Upvotes: 2

abarnert
abarnert

Reputation: 365925

As others have explained, there are two problems with your function:

  1. It's not tail-recursive, so it can only handle lists as long as sys.getrecursionlimit.
  2. Even if it were tail-recursive, Python doesn't do tail recursion optimization.

The first is easy to solve. For example, see Óscar López's answer.

The second is hard to solve, but not impossible. One approach is to use coroutines (built on generators) instead of subroutines. Another is to not actually call the function recursively, but instead return a function with the recursive result, and use a driver that applies the results. See Tail Recursion in Python by Paul Butler for an example of how to implement the latter, but here's what it would look like in your case.

Start with Paul Butler's tail_rec function:

def tail_rec(fun):
    def tail(fun):
        a = fun
        while callable(a):
            a = a()
        return a
    return (lambda x: tail(fun(x)))

This doesn't work as a decorator for his case, because he has two mutually-recursive functions. But in your case, that's not an issue. So, using Óscar López's's version:

@tail_rec
def tail_len(lst):
    def loop(lst, acc):
        if not lst:
            return acc
        return lambda: loop(lst[1:], acc + 1)
    return lambda: loop(lst, 0)

And now:

>>> print tail_len(range(10000))
10000

Tada.

If you actually wanted to use this, you might want to make tail_rec into a nicer decorator:

def tail_rec(fun):
    def tail(fun):
        a = fun
        while callable(a):
            a = a()
        return a
    return functools.update_wrapper(lambda x: tail(fun(x)), fun)

Upvotes: 2

Paul Rubel
Paul Rubel

Reputation: 27232

Imagine you're running this using a stack of paper. You want to count how many sheets you have. If someone gives you 10 sheets you take the first sheet, put it down on the table and grab the next sheet, placing it next to the first sheet. You do this 10 times and your desk is pretty full, but you've set out each sheet. You then start to count every page, recycling it as you count it up, 0 + 1 + 1 + ... => 10. This isn't the best way to count pages, but it mirrors the recursive approach and python's implementaion.

This works for small numbers of pages. Now imagine someone gives you 10000 sheets. Pretty soon there is no room on your desk to set out each page. This is essentially what the error message is telling you.

The Maximum Recursion depth is "how many sheets" can the table hold. Each time you call python needs to keep the "1 + result of recursive call" around so that when all the pages have been laid out it can come back and count them up. Unfortunately you're running out of space before the final counting-up occurs.

If you want to do this recursively to learn, since you're want to use len() in any reasonable situation, just use small lists, 25 should be fine.

Some systems could handle this for large lists if they support tail calls

Upvotes: 1

cleg
cleg

Reputation: 5022

Python isn't optimising tail recursion calls, so using such recursive algorythms isn't a good idea. You can tweak stack with sys.setrecursionlimit(), but it's still not a good idea.

Upvotes: 0

Related Questions