Sunday, June 24, 2012

Tail recursion

In my previous post I compared two solutions, one imperative, one functional. You might have thought that this proves that functional solutions are inherently slower than imperative. That's not true as such. It is better to say that with excessive use of tail recursion you can be as fast as, but your code won't be any more readable. Here's a pure solution that finishes in about the same time.
import scala.annotation.tailrec
def solve(a:Int, b:Int) = {
  @tailrec def solve(sum:Int, n:Int):Int = {
    @tailrec def tens(n:Int, t:Int):Int =
      if (n < 10) t else tens(n/10, t*10)
    val t = tens(n, 1)
    @tailrec def recycle(sum:Int, m:Int):Int = {
      if (n==m) return sum
      recycle(
        if (n < m && m <= b) sum+1 else sum,
        m/10 + m%10*t)
    }
    val newSum = recycle(0, n/10 + n%10*t) + sum
    if (n==b) {
      newSum
    } else {
      solve(newSum, n+1)
    }
  }
  solve(0, a)
}

This shows the rather trivial way of how you can convert any imperative loop into a tail recursive pure function. Of course, the result is still nothing more than an imperative function, obfuscated to fit into the functional rules - giving you the worst of both worlds.

Note: the @tailrec annotations are not necessary, they are only there to ensure that the code I wrote is actually tail-recursive. If not, the compiler will throw an error. This is similar to the @override annotation in java.

No comments: