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


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.

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


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


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.


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.


  • Ruby bug appears only when using print statements inside a block for array.each
  • javascript array numerical key resulting in excess “undefined”
  • Simple regex for domain names
  • Recursion in ASP.NET Core Razor views
  • Setting a relative path to sqlite database with Delphi and Firedac
  • How to distribute Java-based software?
  • Is C++ compilable with OpenMP and boost on MacOS?
  • Is there a equivalent to JSON.Net in Java? [duplicate]
  • How to fallback to entirely different index page if user has javascript disable?
  • Perl function name clash
  • Cassandra 2.1: Recursion by nesting UDT's
  • Creating My Symmetric Key in C#
  • date format change with DT and shiny
  • What is the best way to debug Bootstrap.groovy?
  • @tailrec why does this method not compile with 'contains a recursive call not in tail position&
  • C++ cout and enum representations
  • Bad interaction between Zope2 XML-RPC and AT Image mutator?
  • Time out Error in send mail
  • How can we prepend rows to a react native list-view?
  • Synchronize windows folders
  • Getting short path in python
  • Android changing fragment order inside FragmentPagerAdapter
  • Django model inheritance, filtering models
  • Jquery popup on mouse over of calendar control
  • How can I set a binding to a Combox in a UserControl?
  • Does it make sense to call System.gc() and Thread.sleep() when working on Bitmaps?
  • How to write order and limit within cakephp joins array
  • How do I get HTML corresponding to current DOM tree?
  • Content-Length header not returned from Pylons response
  • Play WS (2.2.1): post/put large request
  • How to create a file in java without a extension
  • Django rest serializer Breaks when data exists
  • How to rebase a series of branches?
  • How to access EntityManager inside Entity class in EJB3
  • Azure Cloud Service Web Role web pages do not load
  • Problems to linebreak with an int in JLabel
  • How to handle AllServersUnavailable Exception
  • vba code to select only visible cells in specific column except heading
  • what is the difference between the asp.net mvc application and asp.net web application
  • ORA-29908: missing primary invocation for ancillary operator