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

21–30 of 87 posts

Re: Tail recursion in Python

#21

Post by pflanze »

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…

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.

Re: Tail recursion in Python

#23

Post by kqr »

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.

Re: Tail recursion in Python

#24

Post by stunt »

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.

Re: Tail recursion in Python

#25

Post by iainmerrick »

__s wrote: post #22

A patch that implements TCO in Python with explicit syntax like 'return from f(x)' could likely get accepted, ending these hacks

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.

Re: Tail recursion in Python

#26

Post by wyager »

pflanze wrote: post #21
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…

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.

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

Re: Tail recursion in Python

#27

Post by shakna »

__s wrote: post #22

A patch that implements TCO in Python with explicit syntax like 'return from f(x)' could likely get accepted, ending these hacks

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

Re: Tail recursion in Python

#28

Post by zielmicha »

pflanze wrote: post #21
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…

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

Re: Tail recursion in Python

#29

Post by _jal »

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?

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

Re: Tail recursion in Python

#30

Post by pjmlp »

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?

Yep, a cheap way to minimize ads, tracking and browser exploits.

Also avoiding downloading JS libraries bigger than Quake while on the go.

Post reply on HN