My Adventures in Coding

June 20, 2010

Tail Recursion in Scala: A Simple Example

Filed under: Scala,UberConf 2010 — Brian @ 8:39 pm
Tags: , , ,

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.

Advertisements

6 Comments »

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

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

  2. 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 | Reply

  3. 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 | Reply

    • 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 | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: