What is the difference between recursion and tail recursion?

Question

In functional programming languages, it is said that it is possible to avoid stack bursts using "tail recursion". But what is the difference between normal recursion and tail recursion?

Answer 1

The difference is precisely where the recursive call is called: If it is called in the "tail" of the function, it is a recursive tail call.

The "tail" of the function is its last call. It is the last computation / calculation done by the function, and soon after it, no treatment is done before returning its value.

For example, considering this function to calculate the factorial of a number, in F#:

let rec fatorial n : int64 = if n <= 1L then 1L else n * fatorial (n - 1L)

This function calculates the factorial of any number you put in. Unless that number is too large. Because in this function, with each recursive call, the stack increases, and a very large number can cause a stack to overflow. Imagine your execution:

fatorial(5) -> 5 * fatorial(5 - 1) ->
5 * fatorial(4) -> 5 * 4 * fatorial(4 - 1) ->
5 * 4 * fatorial(3) -> 5 * 4 * 3 * fatorial(3 - 1) ->
5 * 4 * 3 * fatorial(2) -> 5 * 4 * 3 * 2 * fatorial(2 - 1) ->
5 * 4 * 3 * 2 * fatorial(1) -> 5 * 4 * 3 * 2 * 1 ->
120

If you observe, at each recursive call, the number of functions being called increases, because the program can only calculate the result of the last called function, and then calculate the result of the called functions. So the pile bursts.

How to avoid this? Using recursive tail calls. Functional language compilers often turn tail recursive calls into loops, because this is perfectly possible. Why not do in links directly? Because this would lose the qualities and advantages of functional programming.

I will illustrate a factorial function in F# using tail recursive calls:

let fatorial n =
  let rec _fatorial n acc : int64 =
    if n <= 1L then acc else _fatorial (n - 1L) (acc * r)
  _fatorial n 1L

Note that in this case the recursive function is NOT fatorial, and yes _fatorial. I declared _fatorial inside fatorial so that we can call it with just one argument, and the recursive function uses an accumulator.

The main difference is that in the recursive tail function, the tail call is the recursive call, not * as in the first case. If you look at the call flow, it runs like this:

fatorial(5)       ->
_fatorial(5, 1)   -> _fatorial(5 - 1, 1 * 5)  ->
_fatorial(4, 5)   -> _fatorial(4 - 1, 5 * 4)  ->
_fatorial(3, 20)  -> _fatorial(3 - 1, 20 * 3) ->
_fatorial(2, 60)  -> _fatorial(2 - 1, 60 * 2) ->
_fatorial(1, 120) -> 120

As you can see, at each step, the number of calls neither increases nor decreases. From the moment the recursive function is called, only it is called at the end, without needing further calculations.

When a compiler ready for this sees a recursive call on the tail, it automatically transforms it into a loop during optimizations. With this, you don’t lose the advantages nor the elegance of functional programming, but you also don’t run the risk of going through a stack burst.

Using a reflector, I can see that the recursive function code would look like this, imperatively (in C#):

internal static long _fatorial@8(long n, long acc)
{
  while (n > 1L)
  {
    long arg_1F_0 = n - 1L;
    acc *= n;
    n = arg_1F_0;
  }
  return acc;
}

public static long fatorial(long n)
{
  return Fatorial._fatorial(n, 1L);
}

The compiler actually transforms its recursive function into a loop. On the other hand, the function that does not use cause recursion remains intact.

A good way to know if your function uses tail recursion or not is to try to simulate it in Clojure. Since Clojure does not feature tail recursiveness natively, you should use the function recur, which will make an exception if not used on the tail.

; Causa uma exceção pois a chamada de cauda é *
(defn fatorial [n]
  (if (<= n 1)
      1
      (* n (recur (dec n)))))

; Funciona pois a chamada de cauda é recur
(defn fatorial
  ([n] (fatorial n 1))
  ([n acc] (if (<= n 1)
               acc
               (recur (dec n) (* acc n)))))

Answer 2

Conceptually the execution of a program (process) occurs as follows: The program is loaded in memory. Each program instruction corresponds to a (memory) address. During function call, the following procedure is executed:

1. Current program position is stacked.
2. All local variables and parameters are stacked.
3. All function parameters are stacked.
4. Execution jumps to the position corresponding to the function to be executed.
5. The parameters are popped.
6. Life goes on... (lines run from that point).
7. At the end of the function the process pops the deviation to the program position where it was called.
8. And finally pops the local variables and parameters of the point where the call occurred.

This means that at each function call, the execution stack receives all the information that is in the local scope and a lot of commands to stack and pop occur. If many calls occur the chances are that there will be a burst of this stack. By the way, the name given for these operations that allow to exchange local variables between functions is context change.

Whenever recursion is chosen all problems related to context change can occur (therefore, more operations to manipulate the stack and eventually the stack overflow). But, noting that recursive algorithms could be transformed iterative algorithms, compiler designers created optimizations for some function calls. One such optimization is Tail Call Optimization (TCO).

Works exactly as explained by @Andre-leria with the following remarks:

1. The call sequence of A -> B -> C -> A is also recursive, and would also be subject to optimization for tail call. Some compilers/interpreters can perform optimization on recursions involving more than one function: Ex: Erlang. Scala, for example, can only ensure tail optimizations for the same function (http://www.scala-lang.org/docu/files/ScalaByExample.pdf):

   In principle, Tail calls can Always Re-use the stack frame of the Calling Function. However, some run-time Environments (such as the Java VM) Lack the Primitives to make stack frame Re-use for Tail calls efficient. A Production quality Scala implementation is therefore only required to Re-use the stack frame of a directly Tail-recursive Function Whose last action is a call to itself. Other Tail calls Might be Optimized also, but one should not rely on this Across implementations.

2. Some compilers use a structure called a springboard that turns a call into a tail, in an iteration with accumulators. This happens for example in Scheme which converts the source code to C which does not support TCO.