It's a neat trick; Clojure <http://clojuredocs.org/clojure.core/trampoline> actually uses the same idea, built into the standard library, because while Clojure is functional the JVM doesn't support TCO either (boo!). You have to admit, though, that the UI for this is pretty lacking; just convert all your functions to return closures and call them through `trampoline`? Hmm... surely we can do better than that, right?
Seeing this thread I figured I'd take up the challenge, and I last night I managed to trim this down to: using Lazy @bounce even(n) = n == 0 ? true : odd(n-1) @bounce odd(n) = n == 0 ? false : even(n-1) even(10^6) Tada! Just wrap your functions in @bounce and you're done, no brainpower or funny business at the callsite required. It's also just as fast as Zach's by-hand version (which is to say not very). Technically this covers all tail recursion, but for simple cases you probably want the faster (though more limited) @rec macro, which takes Steven Johnson's excellent advice so you don't have to; i.e. it transforms your code into a nice loop for you. I was testing this recently and realised that @rec zero(n) = n == 0 ? n : zero(n-1) actually gets optimised down to `return 0`, which is pretty neat. Not sure if this will actually be useful to anyone, but there we have it. On Wed, 8 Jul 2015 at 00:11 Stefan Karpinski <[email protected]> wrote: > You can only do TCO if the recursive call is in tail position, which > implies that you are linearly traversing the data structure and not doing > any backtracking. In which case you *can* just use a loop. The value > proposition of using recursion to traverse a recursive data structure (e.g. > visiting all the nodes in a tree) is that you can avoid keeping an explicit > stack of nodes to revisit by using the implicit function call stack. If you > can do TCO, however, that necessarily implies that you didn't need a stack > – implicit or explicit – which means that you can do it with a loop. > > On Wed, Jul 8, 2015 at 12:50 AM, Steven Sagaert <[email protected]> > wrote: > >> The point was doing it using recursion not iteration. When the data >> structures themselves are recursive, a recursive algorithm can be a lot >> simpler/shorter/more elegant than iteration. That's kind of the whole point >> of functional programming. >> >> >> On Tuesday, July 7, 2015 at 9:28:01 PM UTC+2, Steven G. Johnson wrote: >>> >>> >>> >>> On Tuesday, July 7, 2015 at 11:11:19 AM UTC-4, Steven Sagaert wrote: >>>> >>>> see http://blog.zachallaun.com/post/jumping-julia to work around not >>>> having TCO and still use recursion to traverse LARGE data structures >>>> without stackoverflow. That's also how a bunch of other languages (e.g. >>>> Scala & F#) do this (called "trampolining"). >>>> >>> >>> (You could also just use a loop.) >>> >> >
