CODEWITHSUNDEEP
scalarecursion
Phil
Phil

Reputation: 3562

Scala Tail Recursion

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?

Upvotes: 3

Views: 478

Answers (1)

Micho
Micho

Reputation: 3963

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))

Upvotes: 8

Related Questions