How tail recursion works internally in scala?

Question

I am not able to understand tail recursion.

How accumulator variable store intermediate values of recursive calls?
What is the flow of execution. who executes first and why return value fact(n,1)?

def trec(n: Int): BigInt = {

  @tailrec
  def fact(x: Int, accumulator: BigInt): BigInt = {
    if (x <= 1) accumulator else fact(x - 1, x * accumulator)
  }

  fact(n,1)
}

println(trec(5))

If the execution order is not clear to you from the code then you need to go back to some basic lessons on programming Scala before worrying about how recursive functions are implemented and optimised. — Tim, Jul 07 '21 at 07:50
@Tim in the case of scala, I don't reckon it's basic stuff to know how the language optimizes tail calls. All users need to know is how to write tail calls and that `@tailrec` avoids memory errors (correct me if I'm wrong, it's been a while) — joel, Jul 07 '21 at 17:56
@joel I was referring to the question about flow of execution. If the OP doesn't even know how execution flows, how can they understand how Scala optimises the code? Even the accepted answer fails to distinguish properly between tail call elimination and loop optimisation. — Tim, Jul 07 '21 at 21:35

score 2 · Accepted Answer · edited Jul 07 '21 at 20:22

The recursion is support by how code execution works. Whenever you make a call to a method this call is pushed into a stack and all other methods called inside this one is pushed on top of the first, only when the method execution finishes the method call is popped from the stack and its return value is available for the outer method that called it to use it.

This way the recursion works because the results of the previous calls are stored in the stack and each call of the method uses the previous value that has already calculated.

The case of tail recursion specifically is that because the recursive call is the last thing done inside the method you don't need to push one call above the other in the stack (that may cause stack overflow exception) because the previous call has already finished. And because of that when you use @tailrec in scala it converts it to a loop under the hood that is more efficient.

So now I am going to try to answer your questions:

each call to the method has in its accumulator parameter the accumulated value of the factorial so far. The sequence is something like

fact(5, 1) -> fact(4, 5 * 1) -> fact(3, 4 * 5 * 1) -> fact(2, 3 * 4 * 5 * 1) -> fact(1, 2 * 3 * 4 * 5)

So in the last one call the accum parameter has already the result

The flow is first you call the trec method with the value you want to calculate and then this methods call its internal fact method passing also the value that you want to calculate and the accumulator that in this case is the neutral element in multiplication, 1. And then the flow is the one that I have written in step 1 following the recursion

afaik scala optimizes `@tailrec` functions to loops, so they're not executed as functions. See https://stackoverflow.com/a/1682912/5986907 — joel, Jul 07 '21 at 17:50
It is just has I said in my answer just after axplain how normal recursion works — JArgente, Jul 07 '21 at 18:13

How tail recursion works internally in scala?

1 Answers1