The difference is exactly where the recursive call is called: if it is called on the "tail" of the function, it is called the recursive tail.
The function's "tail" is your last call. This is the last calculation / calculation performed by the function, and right after, 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 entered. Unless this number is very high. Because in this function, with each recursive call, the stack increases and a very large 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 ->
If you observe, on each recursive call, the number of functions called increases, because the program can only calculate the result of the last function called, then calculate the result of those who called it. Thus, the stack overflows.
How to avoid this? Use of recursive queue calls. Functional language compilers often transform recursive queue calls into loops, as this is perfectly possible. Why not do it directly? Because it would lose the qualities and benefits of functional programming.
I will illustrate a factorial function in F # using recursive tail 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 said _
fatorial so we can call it with a single 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 observe the flow of the call, it will run as follows:
_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. As soon as the recursive function is called, only it is called at the end, without further calculations.
When a compiler ready to do so sees a recursive call at the tail, it automatically transforms it into a loop during optimizations. With that, you don't lose the benefits or elegance of functional programming, but you also don't run the risk of encountering a stack overflow.
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;
public static long fatorial(long n)
return Fatorial._fatorial(n, 1L);
The compiler actually turns its recursive function into a loop. On the other hand, the function which does not use the cause of recursion remains intact.
A good way to find out whether or not your function uses tail recursion is to try to simulate it in Clojure. Since Clojure has no native tail recursion, you should use the
recur, which will throw an exception if it is not used on the tail.
; Causa uma exceção pois a chamada de cauda é *
(defn fatorial (n)
(if (<= n 1)
(* n (recur (dec n)))))
; Funciona pois a chamada de cauda é recur
((n) (fatorial n 1))
((n acc) (if (<= n 1)
(recur (dec n) (* acc n)))))