4 ms·
Python lacks the tail recursion optimizations common in functional languages like lisp. Seems like the language designers favor iteration instead of recursion,
by scardine 11y ago
Python lacks the tail recursion optimizations common in functional languages like lisp. Seems like the language designers favor iteration instead of recursion, because recursion is limited to a depth of ~1000 on the default implementation (see sys.getrecursionlimit).
It is always possible to convert recursive into iterative, and most of the time doing so is trivial. I recommend doing this unless your algorithm is O(log n) or better.
- dorfsmay 11y agoIs that true even with "generator expression" (Python's lazy evaluation)?
- solipsism 11y agoGenerators take the guts of a loop and make them first class. In order to evaluate that generator incrementally, you still need to provide a loop or a recursive function.
- groovy2shoes 11y agoThe OCaml version presented in the video isn't tail-recursive, either.
- jakeogh 11y agoaaah. The recursion limit. So sum() fails on large inputs.
- agumonkey 11y agoThe functional bits of python were a very early addition by a colleague of GvR, he never wanted lambdas, map and such to be in python.
- jakeogh 11y agoFor anyone curious, @ 15 min https://www.youtube.com/watch?v=r75X4Vn_E9k https://www.youtube.com/watch?v=r75X4Vn_E9k discusses a recursive sum() and why getrecursionlimit() is there.
- scardine 11y agoExcelent resource! I could not put it better than Gavin Bong in this talk "Functional Programming in Python for the Uninitiated". Thanks!
- thedufer 11y agoEven if Python did tail-recursion optimization, this implementation isn't tail-recursive so it would fail in the same way. This version is: def sum(li, s=0): if len(li) == 0: return s else: return sum(li[1:], li[0] + s)