2410 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
</pre>

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:])

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.

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])

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

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

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.

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

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)

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