Sunday, 4 May 2014

Tail Recursion

As I work my way through my Course on Scala², I'm learning a thing or two about functional programming. I am also learning a lot about recursion.

Some of it is also applicable to Java.

It was sufficiently new and surprising to me that I felt it deserved a blogpost. You can find all sorts of information about it elsewhere on the web as well.

No Recursion

What we are used to programming in Java is working iteratively, i.e. loops.

So, let us say we wish to compute the factorial³, we simply use a loop.

Recursion

However, computing a Factorial has always been a very often used example to demonstrate the power of Recursion.

Unfortunately, there's a problem regarding recursion in Java.

Seeing as the method is calling itself, it keeps pushing the stack frames of the method on the stack, before calling itself. This causes a huge increase in memory, as you no doubt know. For all but trivial problems, this results in:

Testcase: factorialTest[28](FactorialTest): Caused an ERROR
java.lang.StackOverflowError
at java.math.BigDecimal.negate(BigDecimal.java:2088)
at java.math.BigDecimal.subtract(BigDecimal.java:1267)
at recursion.Recursion.factorial(Recursion.java:30)

The above message is from the JUnit tests in my project⁶. It works fine, up to the last testcase, where a factorial of 10000 is requested.

Tail Recursion

The following is almost verbatim from the Scala course²:

“In general, if the last action of a function consists of calling a function (which may be the same), such final calls are called tail calls¹.”

“If a function calls itself as its last action, this is called tail recursion.”

“If a function calls itself as its last action, the function's stack frame can be reused. This is called tail recursion optimization.”

In the example of the chapter above, unfortunately, the recursion is not actually tail recursion. As you can see, after the recursion there is still the small matter of the multiplication to do. The multiplication is actually the last operation of the method.

So we need to rewrite the factorial to make use of an accumulator.

“Tail recursive functions are iterative processes.”

This means that a tail recursive function, if the compiler is any good, can be changed into what is effectively a loop. For more in depth information on what happens, see [5].

Notes

Scala does implement Tail Recursion Optimization. Unfortunately, Java does not. This means that in my project⁶ the last test case will fail in Recursion.java as well as TailRecursion.java with a StackOverflowError.

Tail recursion is often used in functional programming, and Java 8 has introduced lambdas which make functional programming a reality for Java. Therefore it is a shame that this optimization is not provided in Java (yet).

Efforts are underway to remedy this⁴.

I hear the syntax would look something like this:

return goto factorial(accumulator.multiply(n), n.subtract(BigDecimal.ONE));

One of the disadvantages is that this optimization makes it (a little) harder to examine stack-traces. But in my opinion, we can surmount this small obstacle easily.