What is the difference between recursion and tail recursion?

Question:

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

Answer:

The difference is just 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 right after that, no processing 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 enter. Unless that number is very large. Because in this function, with each recursive call, the stack grows, and too large a number can cause a stack 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, with each recursive call, the number of functions being called increases, because the program can only calculate the result of the last function called, and then calculate the result of the ones that called it. Thus, the stack overflows.

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

I'm going to 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 , but _ fatorial . I declared _ fatorial inside fatorial so that we can call it with just one argument, the recursive function uses an accumulator.

The main difference is that in the tail recursive function, the tail call is the recursive call, not * as in the first case. If you look at the flow of the call, it goes 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. Once the recursive function is called, it is only called at the end, without further calculations.

When a ready-made compiler sees a recursive call in the tail, it automatically loops it during optimizations. As a result, you don't lose the advantages and elegance of functional programming, but you don't risk a stack overflow either.

Using a reflector, I can see that the recursive function code would imperatively look like this (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 turns your recursive function into a loop. On the other hand, the function that doesn't use cause recursion remains intact.

A good way to tell if your function uses tail recursion or not is to try to simulate it in Clojure. As Clojure doesn't have tail recursion natively, you should use the recur function, which will throw an exception if not used in 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)))))
Scroll to Top