^{2}, 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

^{3}, 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)

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

^{6}. 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

^{2}:

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.“In general, if the last action of a function consists of calling a function (which may be the same), such final calls are calledtail calls^{1}.”

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

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

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

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].“Tail recursive functions are iterative processes.”

# Notes

Scala does implement Tail Recursion Optimization. Unfortunately, Java does not. This means that in my project^{6}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

^{4}.

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.

# References

- [1] Wikipedia - Tail call
- http://en.wikipedia.org/wiki/Tail_call
- [2] Coursera - Functional Programming Principles in Scala
- https://www.coursera.org/course/progfun
- [3] Wikipedia - Factorial
- http://en.wikipedia.org/wiki/Factorial
- [4] OpenJDK Wiki - TailCalls
- https://wiki.openjdk.java.net/display/mlvm/TailCalls
- [5] Dr Dobb's - Tail Call Optimization and Java
- http://www.drdobbs.com/jvm/tail-call-optimization-and-java/240167044
- [6] GitHub - Three Java implementations of Factorial (n!) using NoRecursion, Recursion and TailRecursion
- https://github.com/maartenl/recursion
- Scala Documentation - Glossary
- http://docs.scala-lang.org/glossary/

Thank you! I shall keep at it.

ReplyDelete