Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Tail recursion in Python

chrispenner.ca

Post reply on HN
Print view View original

61–70 of 87 posts

Re: Tail recursion in Python

#61

Post by kahnjw »

naveen99 wrote: post #57
shakna wrote: post #15

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 [0] https://docs.python.org/3/library/functools.html#functools.l...

Is that really tail recursion though ? Seems like you are making two recursive calls to fib(). I thought tail recursion requires a single final call to recursive function. Your memorization helps, but seems you will still run out of stack space if you call it with a big number without a warm up.

I don’t think op is claiming that method is tail recursive, just pointing out you can get away with using recursion and LRU cache.

Re: Tail recursion in Python

#62

Post by [deleted] »

_jal wrote: post #29
roryhughes wrote: post #13

Earlier quoted context omitted.

JS fully disabled in this day and age?

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-cre...

[deleted]

Re: Tail recursion in Python

#63

Post by pflanze »

bjoli wrote: post #47
pflanze wrote: post #21

Earlier quoted context omitted.

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.

Well, both racket and guile dynamically grows/shrinks the stack. Chicken does not. It turns everything into tail calls and copies the stack when it's full and discards whatever is not in scope (simplified). Gambit seems to also not grow the stack dynamically, but I could be wrong.

First, I'm talking about the stack in Scheme (the high level language), since that's what we are talking about here (you gave map as an example); whether there's a C stack used underneath somewhere only matters in this context if its size is tied to the stack size available to Scheme programs. Also, some might argue that Scheme needs to implement call/cc and hence "can't use a stack" for storing Scheme call frames as that would not be efficient, which is correct if you tie the word "stack" to implementations as a single array only. A singly linked list can also work as a stack[1]. Since Scheme gives first class access to continuations, the "call stack" is sometimes correspondingly called the "continuation stack" instead, which then makes more sense.

[1] https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

Gambit definitely does grow the Scheme continuation stack; if you let it grow infinitely, it increases memory use of the whole process until it swaps or runs into a memory limit set via ulimit -v; in the latter case the Gambit runtime throws an out of memory exception in some situations, or reports an out of memory error and exits the system in others. If the procedure returns, the memory is given back first to the heap and then at some point (if not re-used) to the OS.

With regards to Chicken, as you say, it transforms the code into continuation passing style, allocates every continuation frame first on the C stack and then copies surviving frames into a second zone (it basically uses a generational garbage collector with 2 generations). Each long term continuation frame is essentially allocated on the heap (or whatever it is that the second zone is allocated from). Hence I expect that there is no limit on the size of the continuation stack in Chicken, either.

Re: Tail recursion in Python

#64

Post by daveFNbuck »

abhirag wrote: post #56
daveFNbuck wrote: post #50

Earlier quoted context omitted.

You can only avoid the recursion limit in cases where dynamic programming would also work, as you have to explicitly call the function in reverse stack order to avoid having the stack build up. If you want fib(10000) you need to call fib(1) through fib(9999) first, as if you were implementing a dynamic programming solution. This isn't dismissive. lru_cache is one of my favorites too, but it has limitations.

But that isn't a limitation of lru_cache, for example the same higher order function when used in Clojure i.e. memoize with recur for tail recursion will not cause stack overflow. The stack build up is because python doesn't support tail call optimization, not a limitation of lru_cache, just wanted to make it clear because you can use similar higher order functions in other languages which support tail call optimizat…

I agree that this isn't a limitation of the Platonic ideal of an lru_cache function. I thought we were talking about actual Python code.

Re: Tail recursion in Python

#65

Post by bjoli »

iitalics wrote: post #59
bjoli wrote: post #5

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…

To add onto the point about expanding stacks: What's especially nice about this feature is that it means that you don't need to tune your algorithms to be tail recursive when they could be expressed more clearly as non-tail recursion. Functions like map would actually be less efficient on average if it was tail recursive because you would need to re-iterate the list to reverse it.

With guile and Racket, a non-linear reverse! at the end of a map is as fast as doing a non-tail-recursive map.

There are trade-offs for both. The TCO'd map is a lot faster to restore when using continuations, but is not multi-shot continuation safe.

Re: Tail recursion in Python

#69

Post by msuvakov »

Bromskloss wrote: post #67

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.

It should be:

  def tail_factorial(n, accumulator=1):
    if n == 0: return accumulator
    else: return tail_factorial(n-1, accumulator * n)

Re: Tail recursion in Python

#70

Post by shakna »

__s wrote: post #52
shakna wrote: post #27

Earlier quoted context omitted.

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-el...

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

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]

> 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! - 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/0044...

[1] https://mail.python.org/pipermail/python-ideas/2009-May/0045...

[2] https://mail.python.org/pipermail/python-ideas/2009-May/0045...

Post reply on HN