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:])
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.
Start with Paul Butler's
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)
>>> print tail_len(range(10000)) 10000
If you actually wanted to use this, you might want to make
tail_recinto 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
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) + 1list instances (with lengths
len(lst)). It is probably the best idea to just use the built-in
lendirectly, but I guess it was an assignment.
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.