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?

dec() just decrements by one btw

Phil
– Phil

2017-09-27 06:26:46 +00:00
Commented Sep 27, 2017 at 6:26 — Phil
– Phil, Commented Sep 27, 2017 at 6:26

Micho · Accepted Answer · 2017-09-27 06:39:55Z

8

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

edited Sep 27, 2017 at 6:39

answered Sep 27, 2017 at 6:30

Micho

3,98313 gold badges40 silver badges41 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Phil Over a year ago

Can you explain how adding this extra parameter makes it tail recursive?

Micho Over a year ago

Sure. Edited to include an explanation.

Jörg W Mittag Over a year ago

@PhillipR: Infix operators confuse things in this case. Take a piece of paper and write down the recursive call in pure function call notation, and you will immediately see that the recursive call is not in tail position: plus(result, iter(result, dec(x))). Here, it becomes obvious that the call to iter is wrapped in a call to plus and thus not the last call executed.

Collectives™ on Stack Overflow

Scala Tail Recursion

1 Answer 1

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Related