9 ms·

Tail recursion in Python

• bru 9y ago
  > def tail_factorial(n, accumulator=1): > if n == 0: return 1 > else: return tail_factorial(n-1, accumulator * n) The second line should be "if n == 0: return accumulator"
  • rahimnathwani 9y ago
    0! == 1 EDIT: Oops. As pointed out below, the code is indeed incorrect, and my comment is irrelevant.
    • kelnage 9y ago
      True, but irrelevant. For all values of n > 1, that function will return 1, which is clearly not what the author intended.
• rahimnathwani 9y ago
  Interesting use of exceptions.
  • harryf 9y ago
    Indeed although generally it's usually a bad idea to misappropriate the exception throwing / handling mechanism for other purposes, as it's probably be less well optimised, performance-wise, than other parts of a VM.
    • throwaway110116 9y ago
      not in python. exceptions for flow control are not looked down upon unless it’s gratuitous usage. many frameworks do exactly this.
      • icebraining 9y ago
        Even the language itself does this: if a generator that is being processed by a for loop returns (rather than yield), the language will raise a StopIteration exception, which the for loop with catch and use as a signal that it should exit.
      • oneweekwonder 9y ago
        Yes! the more I dive into general py libraries the more I see `try: import pylib2 except: pylib2 = None` etc,
• bjoli 9y ago
  The hackyness/speed issues aside: When compiling/transpiling/whatever between languages, I have found that relying on regular procedure calls and TCO is generally a lot simpler than having to force the looping facility of one language into the semantics of another language. The only one I can actually imagine porting other loops to is the common lisp loop macro, but that is probably the most flexible looping facility known to man. Edit: and oh, cool thing: racket and guile has expanding stacks and doesn't have a recursion limit other than the whole memory of the computer. This is pretty handy when implementing something like map, since you can write a non-tail-recursive procedure so that you don't have to reverse the list at the end.
  • pflanze 9y ago
    With regards to stacks that can use all of the memory: Gambit and AFAIK Chicken behave that way, too. This is one of the reasons I chose Scheme over OCaml (and Haskell) over a decade ago when looking for a new language to move to.
    • wyager 9y ago
      Haskell does not have a recursion limit. You can freely use as much memory as you want via recursion. It doesn’t even really have a stack in the traditional sense. The STG machine does use a stack for evaluation, but it’s often completely different from what you might expect if function calls in Haskell actually necessarily corresponded to C-style functions. There is a default limit to the physical stack size, but it’s something like 512MB and you can change it with a command line flag. https://wiki.haskell.org/Stack_overflow https://wiki.haskell.org/Stack_overflow
    • zielmicha 9y ago
      Even Python doesn't need to have stack limit - just make sure C stack is large enough (e.g. using ulimit or pthread_attr_setstacksize) and use `sys.setrecursionlimit(1000000000)`.
      • pflanze 9y ago
        Making the C stack large enough is not solving it on 32 bit architectures with enough physical RAM that you can't/don't want to waste address space. And on 64 bit architectures address space isn't a problem, but the memory from a temporary large stack can't be re-used without swapping the old stack contents out which is slow.
• Vosporos 9y ago
  I'm not a pythonista, but this code seems to get rid of the recursion limitation of the interpreter. Does it actually "optimize" things and make the function take a constant space as it is calling itself?
  • ericfrederich 9y ago
    It takes a constant space since it is not even recursive. The decorator makes it a non-recursive function with a loop. It'll effectively side-steps the recursion limit in Python. For runs under the limit anyway, it'd be interesting to see whether it's any faster. It trades function call overhead for exception handling overhead. By the way, the first example where it has `return 1` is wrong. It shoudl `return accumulator`. Clicking the GitHub link someone suggested this in December.
• leowoo91 9y ago
  This can also be done using trampolines without using try/catch method: https://github.com/0x65/trampoline https://github.com/0x65/trampoline
• jwilk 9y ago
  Code snippets you won't see if you have JS disabled: https://gist.github.com/ChrisPenner/c0b3f4feb054daa2f6370d2e9961d6d3 https://gist.github.com/ChrisPenner/c0b3f4feb054daa2f6370d2e... https://gist.github.com/ChrisPenner/c958afbf6e7a763c188d8b83275751bb https://gist.github.com/ChrisPenner/c958afbf6e7a763c188d8b83...
  • roryhughes 9y ago
    JS fully disabled in this day and age?
    • abstractbeliefs 9y ago
      It's more common than you think.
      • cglace 9y ago
        But still pretty uncommon.
    • oneweekwonder 9y ago
      opt-in rather then no opt-out?
    • kowdermeister 9y ago
      Only on Hacker News :)
    • _jal 9y ago
      I've noticed a shift over the last while how privacy-protective people are becoming "out-group" and a little weird. I mean, I personally don't care; I've always been a little weird. But it is funny to see technical preferences as a signaling mechanism. Funny, that is, until it hits a certain point... http://www.wired.co.uk/article/chinese-government-social-credit-score-privacy-invasion http://www.wired.co.uk/article/chinese-government-social-cre...
      • 9y ago
• shakna 9y ago
  Someone recently pointed out to me you can bypass the recursion limit with an inbuilt decorator, because it's basically a memoiser. lru_cache, from the functools library. The example given in the docs [0] is: import functools @functools.lru_cache(maxsize=None) def fib(n): if n < 2: return n return fib(n-1) + fib(n-2) [0] https://docs.python.org/3/library/functools.html#functools.lru_cache https://docs.python.org/3/library/functools.html#functools.l...
  • kqr 9y ago
    This only works in specific cases (namely those where dynamic programming algorithms suffice), and does not avoid the recursion limit in general.
    • abhirag 9y ago
      Don't dismiss one of my favorite higher order functions so soon :) "Recursion + memoization provides most of the benefits of dynamic programming, including usually the same running time." -- Steven Skiena lru_cache decorator is great for people who are happy to let the language handle the caching of results for them, and often leads to code which is much more concise than the dynamic programming approach. The limitation you are referring to is that the decorator uses a dictionary to cache results and that dictionary uses the arguments as keys so the arguments need to be hashable. That limitation can be avoided by using immutable data structures (Clojure also has a higher order function called memoize which does the same thing and has no limitations because the core data structures in Clojure are immutable) and although Python not having structural sharing can mean that this approach can hurt memory and GC efficiency a bit, but that trade-off is at least worth considering :) Still have to keep the stack depth less than sys.getrecursionlimit() so no substitute for tail recursion but surely a substitute for dynamic programming in a lot of cases.
      • deleted 9y ago
        [deleted]
      • daveFNbuck 9y ago
• Bogdanp 9y ago
  You can also do this by rewriting functions with a decorator. https://github.com/Bogdanp/tcopy https://github.com/Bogdanp/tcopy
• __s 9y ago
  A patch that implements TCO in Python with explicit syntax like 'return from f(x)' could likely get accepted, ending these hacks
  • iainmerrick 9y ago
    That would be great, especially as it doubles as an annotation/assertion that TCO is both expected and required at that specific point in the code.
  • shakna 9y ago
    Would it? My impression is that Guido is fairly against any such thing occurring [0]. > So let me defend my position (which is that I don't want TRE in the language). If you want a short answer, it's simply unpythonic. [0] http://neopythonic.blogspot.com.au/2009/04/tail-recursion-elimination.html http://neopythonic.blogspot.com.au/2009/04/tail-recursion-el...
    • __s 9y ago
      His primary concern is with implicit tail recursion I tried making such a patch in the past, got stuck in the much of trying to update the grammar file in a way that wouldn't complain about ambiguity Main thing to get from tail calls vs loops is the case of mutually recursive functions
      • shakna 9y ago
        His primary concern seems more to be stack traces. At the time, an explicit style, with patch, was proposed to python-ideas. [0] It was based around continuation-passing-style, and the conclusion reached then by the community was the same. TCO, explicit or not, isn't wanted in Python. > And that's exactly the point -- the algorithms to which TCO can be applied are precisely the ones that are not typically expressed using recursion in Python. - Greg Ewing [1] > <sarcasm>Perhaps we should implement "come from" and "go to" while we're at it. Oh, let's not leave out "alter" (for those of you old enough to have used COBOL) as well! </sarcasm> - Gerald Britton [2] Feel free to try again, maybe things have changed. To be clear, I wish Python did have a mechanism to express these sorts of problems, but I don't think the Python team themselves want them. This issue has come up more than a few times, and the dev team have never been satisfied that Python really needs it. [0] https://mail.python.org/pipermail/python-ideas/2009-May/004430.html https://mail.python.org/pipermail/python-ideas/2009-May/0044... [1] https://mail.python.org/pipermail/python-ideas/2009-May/004522.html https://mail.python.org/pipermail/python-ideas/2009-May/0045... [2] https://mail.python.org/pipermail/python-ideas/2009-May/004536.html https://mail.python.org/pipermail/python-ideas/2009-May/0045...
• stunt 9y ago
  Your code is still allocating a new stack frame anyway. So no optimization is happening. You are simply avoiding a stack overflow which is not the purpose of tail-call optimization. I'm not sure if there is any advantage when language/compiler does not provide a proper tail recursive optimization.
  • quietbritishjim 9y ago
    It's a gross exaggeration to say there's no advantage. Who decided that stack frame re-use is "the purpose" of tail-call optimization, while not blowing the stack is not? It seems to me that being able to run the function at all is more important than whether it runs quickly.
• sifoo 9y ago
  Once you have some kind of virtual machine going; it's not that difficult to delay tail calls until back in the VM loop, which allows the C stack to unwind between calls. This is mostly Guido being ignorant and stubborn, I have a feeling he would get along great with Rob Pike. I've found that having dedicated syntax [0] for tail calls makes life easier for everyone involved. [0] https://github.com/basic-gongfu/cixl#functions https://github.com/basic-gongfu/cixl#functions
• cup-of-tea 9y ago
  This is the same as recur in Clojure. It's not general TCO, though, which is much more powerful. I do think it's a shame that Python doesn't have general TCO. It's said to be unpythonic because it means there will be two ways to do things. But some things are so easily expressed as a recursion but require considerable thought to be turned into a loop.
  • e12e 9y ago
    > But some things are so easily expressed as a recursion but require considerable thought to be turned into a loop. Do you have some examples of problem+solutions where tco works fine (in a language with tco) - but the manual translation is hard(ish)? I wonder in part after reading the Julia thread on tco - and difficulties with providing guarantees in the general case with tco: https://github.com/JuliaLang/julia/issues/4964 https://github.com/JuliaLang/julia/issues/4964
    • lysium 9y ago
      Usually, I implement state machines with mutually tail recursive functions. Each function represents one state.
      • e12e 9y ago
        Right. The general rewrite would be a loop with a switch and state functions that returned a state? (i was going to say state functions that called back to a step function, but I guess that'd still build a call stack).
  • jvandonsel 9y ago
    The nice thing about recur in Clojure is that it won't even compile if the call isn't in the tail position. I've inadvertently made a code change that moved the recur call out of the tail position and the error became immediately obvious. With TCO you might not even notice until your stack blows up on a deep nesting.
  • dragonwriter 9y ago
• orf 9y ago
  I experimented with something similar to this way back[1], but took a slightly different approach - you can replace the reference to the function itself inside the function with a new function[2], one that returns a 'Recurse' object. That way it looks like it's calling the original method but really it's doing your own thing. 1. https://tomforb.es/adding-tail-call-optimization-to-python/ https://tomforb.es/adding-tail-call-optimization-to-python/ 2. https://gist.github.com/orf/41746c53b8eda5b988c5#file-tail_call-py-L16 https://gist.github.com/orf/41746c53b8eda5b988c5#file-tail_c...
• e12e 9y ago
  > def tail_factorial(n, accumulator=1): > if n == 0: return 1 > else: return tail_factorial(n-1, accumulator * n) Does this ever return the accumulator? [ed: ah, no. I see the first comment on the article is about this bug; it should return accumulator, not 1]
• tu7001 9y ago
  I used it to play with some functional programming in Python https://github.com/lion137/Functional---Python https://github.com/lion137/Functional---Python
• Bromskloss 9y ago
  def tail_factorial(n, accumulator=1): if n == 0: return 1 else: return tail_factorial(n-1, accumulator * n) This just returns 1 every time.
  • msuvakov 9y ago
    It should be: def tail_factorial(n, accumulator=1): if n == 0: return accumulator else: return tail_factorial(n-1, accumulator * n)
• a-nikolaev 9y ago
  > It turns out that most recursive functions can be reworked into the tail-call form. This statement in the beginning is not entirely correct. A more accurate statement would be that all recursive programs that are _iterative_ (if they are loops in disguise), can be rewritten in a tail-call form. That is, there must be a single chain of function calls. The inherently recursive procedures cannot be converted into a tail-call form.
• Animats 9y ago
  Tail recursion is a programming idea left over from the LISP era. It's from when iteration constructs were "while" and "for", and there were no "do this to all that stuff" primitives. Python doesn't really need it.
  • yorwba 9y ago
    Tail calls aren't always just used for some simple iteration. For example, you could have several mutually recursive functions calling each other in tail position. If you wanted to turn that into a loop, you'd have to roll all those functions into a single loop body, which would be made even less elegant due to the lack of goto statement. (TCO essentially turns a call into a goto whenever possible.)
    • viraptor 9y ago
      Lots of languages can express it better though - even without gotos. For example in python you can do: while some_condition: x = one_generator(y) y = other_generator(x) where the generators yield values. No need for goto, no TCO, no magic. Even in languages like C, a nicer way to express it may be via two explicit state machines rather than going full Duff's device at this problem.
      • lispm 9y ago
        Python's generators are more magic. It's similar to some kind of COME FROM mechanism.
        • viraptor 9y ago
          Weird comparison. Come from has no indication on the other side that it will happen. Generators are pretty explicit with yield. On the calling side they can be explicit with a next() call.
          • lispm 9y ago
            A generator may have multiple yields, if you call next(), then it comes from that call to the last yield call - based on the current execution context. The yield waits that the execution comes back to it. The idea of function calls is much simpler - no yield magic necessary.
• chapill 9y ago
  Tail recursion is a bad idea in multicore land. You end up with a one sided tree structure that can't be parallel processed.
• quietbritishjim 9y ago
  This article and the other comments here are interesting, but some are trying to be a bit too clever. The original article isn't too bad, but one of the other comments suggests re-writing the contents of the function at run time, which I really don't think is a practical suggestion (think about debugging such a thing). If I wanted to do this in practice, I'd just write the trampoline out explicitly, unless I wanted to do it a huge number of times. Doing it this way only takes a couple of extra lines of code but I think that's worth it for the improvement in explicitness, which is a big help for future maintainers (possibly me!). from functools import partial def _tail_factorial(n, accumulator): if n == 0: return accumulator else: return partial(_tail_factorial, n - 1, accumulator * n) def factorial(n): result = partial(_tail_factorial, n, 1) while isinstance(result, partial): result = result() return result