Tail recursion in Python • Hacker News Board

Re: Tail recursion in Python

#41

Post by [deleted] » Sat, Mar 17, 2018, 3:27 PM UTC

shakna wrote: post #36

d0mine wrote: post #32

Earlier quoted context omitted.

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

[deleted]

Re: Tail recursion in Python

#42

Post by cup-of-tea » Sat, Mar 17, 2018, 3:27 PM UTC

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.

Re: Tail recursion in Python

#43

Post by Can_Not » Sat, Mar 17, 2018, 3:31 PM UTC

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?

No page shows JavaScript for me until I enable it with NoScript. It's too sad that Firefox Focus on Android doesn't allow plugins or disabling JS, it make it makes the whole thing pointless.

Re: Tail recursion in Python

#44

Post by orf » Sat, Mar 17, 2018, 3:34 PM UTC

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/

2. https://gist.github.com/orf/41746c53b8eda5b988c5#file-tail_c...

Re: Tail recursion in Python

#45

Post by nullp0tr » Sat, Mar 17, 2018, 4:00 PM UTC

__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

It's actually not likely at ALL. Guido van Rossum said[0] on multiple occasions that it's un-pythonic and it won't happen.

Edit: I didn't see shakna's comment.

[0] http://neopythonic.blogspot.de/2009/04/tail-recursion-elimin...

Re: Tail recursion in Python

#46

Post by smoe » Sat, Mar 17, 2018, 4:06 PM UTC

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 have started using a "Quick Javascript Switcher" extension some years ago to easily opt-in for certain pages but have js disabled by default.

This was one of the best quality of life decision in terms of web browsing I have ever made.

The vast majority of pages that I randomly access (e.g. from hacker news) are text based and usually work just fine without js. But the time until I can start reading is much faster (less jumping around of content) and I don't get the growth hackers modals shoven down my throat two paragraphs in. The pages I use regularly are usually white listed

Re: Tail recursion in Python

#47

Post by bjoli » Sat, Mar 17, 2018, 4:43 PM UTC

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.

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.

Re: Tail recursion in Python

#48

Post by e12e » Sat, Mar 17, 2018, 4:55 PM UTC

cup-of-tea wrote: post #42

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.

> 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

Re: Tail recursion in Python

#49

Post by e12e » Sat, Mar 17, 2018, 4:59 PM UTC

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

Re: Tail recursion in Python

#50

Post by daveFNbuck » Sat, Mar 17, 2018, 5:05 PM UTC

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…

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.