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

31–40 of 87 posts

Re: Tail recursion in Python

#31

Post by pflanze »

zielmicha wrote: post #28
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.

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)`.

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.

Re: Tail recursion in Python

#32

Post by d0mine »

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

It won't help unless you call it in a specific order e.g., fib(10_000) may produce RecursionError unless you run for n in range(10_000): fib(n)

Re: Tail recursion in Python

#33

Post by dfsegoat »

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

"Blacklist all by default, whitelist as needed" is how we build most secure systems right? I'll admit it feels strange applying that construct to day to day browsing.

Re: Tail recursion in Python

#34

Post by username223 »

roryhughes wrote: post #13
jwilk wrote: post #10

Code snippets you won't see if you have JS disabled: https://gist.github.com/ChrisPenner/c0b3f4feb054daa2f6370d2e... https://gist.github.com/ChrisPenner/c958afbf6e7a763c188d8b83...

JS fully disabled in this day and age?

Flash fully disabled in this day and age? ;-)

More like "disabled by default," actually. It's mostly ads/tracking, popovers, and other annoyances, and it's easy to selectively turn it back on where you really need it. This approach isn't for the general public yet.

Re: Tail recursion in Python

#35

Post by nol13 »

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

battle is over, privacy lost

Re: Tail recursion in Python

#36

Post by shakna »

d0mine wrote: post #32
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...

It won't help unless you call it in a specific order e.g., fib(10_000) may produce RecursionError unless you run for n in range(10_000): fib(n)

Right, it's a memoiser.

You side-step some recursion through previously stored results. It works well for some class of algorithms, which coincides with quite a large subsection of problems where TCO would help formulate algorithms.

There are still a bunch of limits, because you're caching results, not eliminating call frames.

The first obvious drawback is performance and memory use: All results get stored in a dictionary.

Re: Tail recursion in Python

#37

Post by abhirag »

kqr wrote: post #23
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...

This only works in specific cases (namely those where dynamic programming algorithms suffice), and does not avoid the recursion limit in general.

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.

Re: Tail recursion in Python

#38

Post by sifoo »

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

Re: Tail recursion in Python

#39

Post by [deleted] »

abhirag wrote: post #37
kqr wrote: post #23

Earlier quoted context omitted.

This only works in specific cases (namely those where dynamic programming algorithms suffice), and does not avoid the recursion limit in general.

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 limitat…

[deleted]
Post reply on HN