While at UberConf I had the great opportunity to attend a talk titled “Scala for Java Programmers” put on by Venkat Subramaniam, the author of the book “Scala Programming“. In my previous post I gave examples of using XML in Scala. In this post I will walk you through the examples Venkat used to show how to properly do tail recursion in Scala.

##### Recursion

def factorial(number:Int) : Int = { if (number == 1) return 1 number * factorial (number - 1) } println(factorial(5))

In order for a recursive call to be tail recursive, the call back to the function must be the last action performed in the function. In the example above, because the total returned from the recursive call is being multiplied by *number*, the recursive call is NOT the last action performed in the function, so the recursive call is NOT tail recursive. The method calls itself until the parameter passed in equals 1. In this recursive method call, the sequence of calls looks like:

5 * total (5 – 1)

4 * total (4 – 1) = 20

3 * total (3 – 1) = 60

2 * total (2 – 1) = 120

##### Tail Recursion

To take this example and make it tail recursive, we must make sure that the last action performed in the function is the recursive call. To do this we update the *factorial* function to have two parameters. The new *accumulator* parameter stores the intermediate value, so we are no longer doing a calculation against the value returned from the function like we were before.

def factorial(accumulator: Int, number: Int) : Int = { if(number == 1) return accumulator factorial(number * accumulator, number - 1) } println(factorial(1,5))

However, we can still do better! Scala allows a function to be declared inside another function. So here we take the code inside the function and wrap it in a new inner function called *factorialWithAccumulator*. By making this change we avoid changing the parameters of the *factorial* method so no one calling it needs to do anything different.

def factorial(number: Int) : Int = { def factorialWithAccumulator(accumulator: Int, number: Int) : Int = { if (number == 1) return accumulator else factorialWithAccumulator(accumulator * number, number - 1) } factorialWithAccumulator(1, number) } println(factorial(5))

##### Why Tail Recursion?

In the recursion example, notice how the result of each call must be *remembered*, to do this each recursive call requires an entry on the stack until all recursive calls have been made. This makes the recursive call more expensive in terms of memory. While in the tail recursive example, there are no intermediate values that need to be stored on the stack, the intermediate value is always passed back as a parameter.

[…] algorithm uses tail recursion, a compiler optimization […]

Pingback by Jfokus 2011/Citerus Programming Contest | talexandre — March 15, 2011 @ 5:04 am |

[…] First up, simple factoral functions (source: https://myadventuresincoding.wordpress.com/2010/06/20/tail-recursion-in-scala-a-simple-example/): […]

Pingback by Scala tail recursion vs non-tail receursion performance testing with dynaTrace - Mark's IT Blog — July 31, 2012 @ 12:53 am |

[…] https://myadventuresincoding.wordpress.com/2010/06/20/tail-recursion-in-scala-a-simple-example/ […]

Pingback by Accumulator functions | programminglearnedtoday — April 6, 2013 @ 3:59 pm |

NICE! I tried to understand tail recursion on wikipedia, and simply couldn’t. But in this example I saw what you meant on the first glance. As allways, to make something simple you need a genious. like Einstein with his relativity theory. The special relativity theroy has never been explained better than by Einstein himself. Nobody afterwards gave a simpler explanation. I find that most interesting. Though comparing tail recursion with the relativity theory is a little bit far fetched, I know.

Comment by kw4nta — June 14, 2013 @ 2:27 am |

Instead of

def factorial(number:Int) : Int = {

if (number == 1)

return 1

number * factorial (number – 1)

}

println(factorial(5))

By definition the correct implementation should be

def factorial(number:Int) : Int = {

if (number == 0)

return 1

number * factorial (number – 1)

}

println(factorial(5))

Usually we sometime slip on the fact that the base case is 0 and not 1. Factorial is defined for zero too. 🙂

Comment by Nitish Upreti — June 3, 2014 @ 12:15 am |

Here is my version that works also with 0!

def factorial(number: Int) : Int = {

def factorialWithAccumulator(accumulator: Int, number: Int) : Int = {

if (number == 0)

return accumulator

else

factorialWithAccumulator(if (number – 1 > 0) accumulator * (number – 1) else accumulator, number – 1)

}

factorialWithAccumulator(if (number > 0) number else 1, number)

}

Comment by Anna — June 11, 2015 @ 12:04 pm |