Tuesday, April 1, 2014

Exploring Tail Recursion

A tail-recursive function does not require a new stack frame for each call. All the recursive calls will execute in a single frame. This is benefiitial because you do not have to worry about recursing too deeply and getting a StackOverflowError, or the overhead of the many function calls.

What makes a function tail-recursive, and not just recursive, is that the call to itself is the last operation in the function. When this happens the compiler can generate bytecodes that are the same as if the function were written with a while-loop. These two examples from Programming in Scala are not only functionally equivalent, but would be optimized to have the same bytecode:


In Scala use the @tailrec annotation so you will get a compiler error if the function's recursion can not be optimized away.