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?

---

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

链接地址: http://www.djcxy.com/p/80698.html

上一篇: 递归地划分正方形区域

下一篇: 斯卡拉尾递归