Tail Calls

tags : Functional Programming, Programming Languages, Recursion

What and Where? §

• It’s a language runtime feature that certain programming languages provide.
• When a function calls another as its last action
  • caller returns immediately after calling X
  • caller has nothing to do after the calling X
  • X does not really have to return to the caller (we can take advantage of this)
  • That last call to X can now be termed as a tail call
• Doesn’t have to appear lexically after all other statements
• Fundamentally not related to recursion but gets used a lot w it.
• Kind of a jump that passes arguments. kind of goto dressed as a call

Proper tail calls(PTC) and Tail call Optimization(TCO) §

• So we know that a tail call doesn’t need to return to it’s caller. So we can take advantage of it. When we take advantage of this it’s TCO(It’s an umbrella term). Some people also call it tail call elimination but that term never made lot of sense to me.
• Having this optimization means, your stack never grows when it encounters a tail call.
• Some languages like Scheme require tail calls to be optimized by specification. Others may add support for it via different syntax by other means.
• Not every implementation implements PTC+TCO, some may just optimize for recursive calls, some may do something else etc.
• The Optimization: B’s frame is replaced with the frame of C in the same stack.

      // A (main func), B (caller func), C (other func)
      func A()
        func B()
          return C()
        end
        print(B()) // C() will directly return here if TCO
      end

• Disadvantage: RIP stack trace, cuz those frames no longer exist.

Recursive tail calls §

• Like mentioned before tail calls are not related to recursion directly, see this for a good example on using tail calls when recursion is not involved.
• A recursive function is just like any other function, so when we call the function itself in the tail call, we have tail recursion. This may or may not be “optimized”, but general languages that support tail recursion support the optimization.
• w tail recursion + TCO, we get a couple of nice things
  • We get free infinite recursion! No stack overflow. So we can freely write recursive procedures in cases where we’d have to worry about stack overflow.
  • We get a way to run things iteratively. Extensively used in languages without loops.
• A language supporting tail recursion + TCO doesn’t mean normal recursion in that language get optimized too. This is strictly only for tail calls (whatever that mean to the certain language).

Other notes §

• The “remaining computation” —the addition of 1— now happens before the recursive call not after when programmer writes code for tail recursion.
• The tail-call optimization reduces the stack space requirements from linear to constant.
  • i.e From O(n) to O(1)
• How Tail Call Optimization Works