Python recursive function error: “maximum recursion depth exceeded” [duplicate]

by

Recursion is not the most idiomatic way to do things in Python, as it doesn’t have tail recursion optimization thus making impractical the use of recursion as a substitute for iteration (even if in your example the function is not tail-recursive, that wouldn’t help anyway). Basically, that means that you shouldn’t use it for things that have a complexity greater than linear if you expect your inputs to be large, (still it’s OK for doing things that have a logarithmic recursion depth, like divide and conquer algorithms as QuickSort).

If you want to try that approach, use a language better suited to do functional programming, as Lisp, Scheme, Haskell, OCaml, etc.; or give a try to Stackless Python, that has broader limits in stack usage and also has tail recursion optimisation 🙂

By the way, a tail-recursive equivalent of your function could be:

def primeList(n, i=2, acc=None):
    return i > n and (acc or []) or primeList(n, i+1, (acc or []) + (isPrime(i) and [i] or []))

Another “by the way”, you shouldn’t construct a list if you’re using it just to add up the values… The Pythonic way to solve Project Euler’s 10th problem is:

print sum(n for n in xrange(2, 2000001) if all(n % i for i in xrange(2, int(n**0.5)+1)))

(OK, maybe splitting it in various lines would be even more Pythonic, but I love one liners ^_^)

More Related Contents:

  1. Recursive to iterative using a systematic method [closed]
  2. Why does my recursive function return None?
  3. What is the maximum recursion depth in Python, and how to increase it?
  4. Recursive function returning none in Python [duplicate]
  5. Loop through all nested dictionary values?
  6. Python recursion with list returns None [duplicate]
  7. Basics of recursion in Python
  8. Does Python optimize tail recursion?
  9. Return in Recursive Function
  10. Python: Maximum recursion depth exceeded
  11. recursive iteration through nested json for specific key in python
  12. Recursion and return statements
  13. python recursion return None type
  14. How to flatten a nested JSON recursively, with flatten_json
  15. Using self.xxxx as a default parameter – Python
  16. Recursive function returning none? [duplicate]
  17. Setting property causes maximum recursion depth exceeded
  18. How to find common elements in list of lists?
  19. python recursive vectorization with timeseries
  20. Change values in dict of nested dicts using items in a list?
  21. Python: using a recursive algorithm as a generator
  22. How can a recursive regexp be implemented in python?
  23. Recursive diff of two dictionaries (keys and values)?
  24. python recursive function that prints from 0 to n?
  25. Python: maximum recursion depth exceeded while calling a Python object
  26. How do I reverse a list using recursion in Python?
  27. Finding all maze solutions with Python
  28. getattr and setattr on nested subobjects / chained properties?
  29. What is the maximum recursion depth, and how to increase it?
  30. Max recursion is not exactly what sys.getrecursionlimit() claims. How come?

Leave a Comment