4

In the book Functional Programming in Scala, in the context of explaining how recursion is often used in functional programming over imperative iteration, the authors show recursion via a factorial function using a helper function called "go" or "loop", and state that this is standard practice is functional scala programming:

...
def factorial(n: Int): Int = {
  @tailrec def go(n: Int, acc: Int): Int = {
    if (n <= 0 ) acc
    else go(n - 1, n*acc)
  }
  go(n, 1)
}

...but one could just as easily, if not more concisely define it without a helper function thus:

...
def factorial(n: Int): Int = {
  if (n <= 0) 1
    else n * factorial(n - 1)
}

My understanding is that accumulating values and avoiding mutation is achieved in recursion by leveraging the stack frame and "passing" return values to the previous stack frame. Here, the authors appear to using an explicit accumulator parameter for a similar purpose.

Is there an advantage in using helper functions to accumulate values like this, or are they using this example to show how recursion relates to imperative iteration by explicitly passing state to the helper function?

Stef
  • 13,242
  • 2
  • 17
  • 28
Aaron
  • 3,249
  • 4
  • 35
  • 51
  • 4
    because of tailrec (tail recursion optimistation). without it it would be stack overflow (how ironic this question at this site) exception at some point + it is much less efficient – Artem Sokolov Sep 16 '20 at 09:00
  • @ArtemSokolov but the second version wouldn't end in stack overflow would it? It would hit the base-case. Or do you mean that without the annotation you can't have the complier complain if it can't do tail call optimization and you can't put the annotation on the outer function? – Aaron Sep 16 '20 at 09:03
  • Tail recursion doesn't use the call stack but an accumulator, hence the former can be eliminated. Such accumulator style recursion is just a loop under the hood. In a lazy environemnt you have a lazy right fold as an alternative. Lazyness gives rise to stack safety for free. –  Sep 16 '20 at 09:04
  • 2
    @Aaron annotation doesnt apply tail recursion, it only forces compiler to fail if it is not optimised. Second version will fail because of SO, because there is no tailrec optimisation, because there is not a tail recursion structure of the function. – Artem Sokolov Sep 16 '20 at 09:05
  • Ah I see, in the second case there is more work to be done after the recursive call and thus it can't be optimized into a loop by the compiler right? So the first comment should be the answer. If you make it the answer I will mark it as such. – Aaron Sep 16 '20 at 09:05
  • tail recursion optimisation demands that your next function call should be exactly the returning expression – Artem Sokolov Sep 16 '20 at 09:08

2 Answers2

8

Tail recursion is an important optimization that makes recursive functions faster and avoids a "stack overflow" if the recursion is too deep.

Recursion without tail recursion

def factorial(n: Int): Int = {
  if (n <= 0) 1
    else n * factorial(n - 1)
}

What happens when I want to calculate factorial(10)? First, I calculate factorial(9); Then, I multiply the result by 10. This means that while I am calculating factorial(9), I need to keep a note somewhere: "Remember, when you're done with factorial(9), you still need to multiply by 10!".

And then in order to calculate factorial(9), I must first calculate factorial(8), then multiply the result by 9. So I write a little note "Remember to multiply by 9 when you have the result of factorial(8).

This goes on; finally I arrive at factorial(0), which is 1. By this time I have ten little notes that say "Remember to multiply by 1 when you're done with factorial(0)", "Remember to multiply by 2 when you're done with factorial(1)", etc.

Those notes are called "the stack" because they are quite literally stacked on top of each other. If the stack gets too big, the program crashes with a "stack overflow".

Tail recursion

def factorial(n: Int): Int = {
  @tailrec def go(n: Int, acc: Int): Int = {
    if (n <= 0 ) acc
    else go(n - 1, n*acc)
  }
  go(n, 1)
}

The function go in this program is different. In order to calculate go(10, 1) you need to calculate go(9, 10); but when you have finished calculating go(9, 10), you don't need to do anything else! You can return the result directly. So there is no need to keep a little note "remember to multiply the result by 10 after the recursive call". The compiler optimizes this behaviour: instead of stacking the call to go(9, 10) on top of the call to go(10, 1), it replaces the call to go(10, 1) with the call to go(9, 10). Then it replaces the call to go(9, 10) with a call to go(8, 90). So the stack never increases during the recursion. This is called tail recursion because the recursive call is the last thing that happens in the execution of the function (in particular, the multiplication by 10 happens when evaluating the arguments).

Stef
  • 13,242
  • 2
  • 17
  • 28
  • This is a great answer, but Artem answered first in the comments, so gave him the answer. – Aaron Sep 16 '20 at 09:56
  • If this answer is better, why do not change your vote? it is possible to change your accepted answer. – Chema Sep 16 '20 at 10:34
  • I agree with the position that a more precise, clear, and correct post should be marked as an answer if it better suits your original question. Stef's post is great it should be encouraged. – Artem Sokolov Sep 16 '20 at 12:21
  • @Stef no disrespect, I thought cause he answered first I accepted, but I agree your answer is really spot on. Thanks for taking the time. – Aaron Sep 16 '20 at 14:49
  • In the case of tail optimization does the compiler actually convert to the same byte code as would result from a while loop? – Aaron Sep 16 '20 at 14:51
  • 1
    @Aaron: yes. See also https://www.scala-lang.org/api/2.9.2/scala/annotation/tailrec.html and https://stackoverflow.com/questions/23546300/does-tailrec-affect-compiler-optimizations and https://stackoverflow.com/questions/3114142/what-is-the-scala-annotation-to-ensure-a-tail-recursive-function-is-optimized – Stef Sep 16 '20 at 14:55
3

Because of tailrec (tail recursion optimization).

Without it would be a stack overflow (how ironic this question at this site) exception at some point and it is much less efficient (by memory mainly).

Important to note that @tailrec annotation doesn't do or apply tailrec optimization but just enforces the compiler to fail if it couldn't be optimized.

And tail recursion optimization demands that your next iteration function call should be EXACTLY the returning expression (without additional operations or calculations in it).

Artem Sokolov
  • 810
  • 4
  • 8
  • The book didn't quite make it clear that this is why there's a helper function though it did mention tail call optmization. – Aaron Sep 16 '20 at 09:57