Scala Tail Recursion

Question

So I have this recursive function that multiplies two numbers, simple enough.

    def mul(n: Int, m: Int):Int =
        if(m > 1) n + mul(n, dec(m))
        else n

Now I'm trying to turn it into a tail recursive function, and I tried this:

    def mulWithTail(n: Int, m: Int):Int = {
        @tailrec
        def iter(result: Int, x: Int):Int =
            if(x == 0) result
            else result + iter(result, dec(x))
        iter(n, m)
    }

However I get the following error:

error: could not optimize @tailrec annotated method iter: it contains a recursive call not in tail position

else result + iter(result, dec(x))

Question: Can you explain to me why this error is occurring? How should I refactor my code?

Micho Micho · Accepted Answer · 2017-09-27T06:30:52

You can make your function tail recursive simply adding an extra parameter acting like an accumulator. Like this.

def mul(n: Int, m: Int, acc: Int): Int =
  if (m > 1) mul(n, m - 1, n + acc)
  else acc

To make a function tail recursive you must not perform any other operation in the recursion step but calling the function recursively. In your code samples you're performing an addition in the recursion step.

n + mul(n, dec(m))
result + iter(result, dec(x))

Scala Tail Recursion

1 Answers