DEV Community

Recursion, Tail Call Optimization and Recursion.

Edison Yap on November 30, 2018

Recently I thought I'd take a jab at functional languages just to try out a different paradigm of thinking, and I decided to pick up Elixir since i...

Read full post

Mihail Malo • Feb 13 '19

Didn't know there's a flag.
Why isn't it enabled by default?
Seems like a no-brainer optimization to do when the conditions allow it.

Also, it works in all explicit/implicit return positions, right? Not just at the end of the function?

What about mutual recursion with both functions calling each other in tail position?

Edison Yap • Feb 13 '19 • Edited

There are implicit trade-off, such as losing the stack trace which could make things harder to debug.

I think you have to keep in mind though, software is about tradeoffs - just because the condition allow it does not mean the tradeoff is worth it.

One of the most popular use case is recursion, but we don't really do recursions in Ruby, so is it really worth the tradeoff then?

It's also Python's reasoning (Guido). You can read more about his blog posts here explaining his rationale, it's a pretty good read.

1) neopythonic.blogspot.com/2009/04/t...

2) neopythonic.blogspot.com/2009/04/f...

You can also read about the progress on Ruby's official issue tracker - bugs.ruby-lang.org/issues/6602

Yes it doesn't have to literally be on the last line, but just the last executed statement.

Not sure what you mean about mutual calling, I don't think that's really possible (I could be wrong) - Yes, you can mutual call each other at tail call position, but that does not instantly make it possible for tail call optimization; TCO is when a compiler recognizes it's calling itself (as stated in the gifs). TCO also eliminates the stackframe (can read in the issue tracker). I don't think compilers can recognize a mutual calling tail call and optimize that

Mihail Malo • Feb 13 '19 • Edited

ES6 spec mandated TCO for mutually recursive functions as well that both call each other in tail call position.
Only Apple browsers have it implemented at the moment, Chrome implemented it but later removed it.

One notable part of the spec was that

function a(n){
  if (n<=0) return
  a(n-1)
}

would not get optimized, because there is an implicit return undefined after the last line.
I understand how that limitation came about, but I don't really see why they couldn't add a single "void" to the stack and then merrily recurse as if it's this:

function a(n){
  if (n<=0) return
  return a(n-1)
}

since the return value of the inner a is never used.

Mihail Malo • Feb 13 '19

The tradeoffs for Ruby specifically sound like something that is more relevant in development than production, almost like something that should be a flag... Oh. That's what they did. Okay.

(I'd still suggest it be the default, until someone needs to pass --debug, but I get the idea)

JP • Dec 2 '18

Very interesting explanation. I've been using Elixir for a while now, and even though I knew that the BEAM provides tail call optimization, I did not know how it worked behind scenes, it is a goto!

Edison Yap • Dec 2 '18

Glad you liked it man! Yeah it's always interesting to see how things work behind the scene!

JC • Feb 18 '19

Just want to mention that tail call optimization is not always the best solution. Sometimes, it consumes more memory and runs slower than body recursion.

Edison Yap • Feb 18 '19 • Edited

Interesting, can you elaborate on that?

P.S: And welcome to dev.to :D

JC • Feb 19 '19

After Erlang/OTP R12B, a body-recursive function generally uses the same amount of memory as a tail-recursive function and generally hard to predict whether the tail-recursive or the body-recursive version will be faster.
With around 10, 000 elements, a body-reclusive function is about 10% faster. But with larger lists (like 10, 000, 000 elements), a body-reclusive function is about 97% lower and it is about as faster as the standard library map.

references:
Myth: Tail-Recursive Functions are Much Faster Than Recursive Functions
erlang.org/doc/efficiency_guide/my...
TAIL CALL OPTIMIZATION IN ELIXIR & ERLANG – NOT AS EFFICIENT AND IMPORTANT AS YOU PROBABLY THINK
pragtob.wordpress.com/2016/06/16/t...