Tail Recursion

We want to compute sum from 1 + 2 + .. + n

In an imperative programming language, we would write something like

sum = 0
for(int i = 1; i < n; i++){
    sum = sum + i;
}

In a functional programming language, we don't have looping mechanism. We will have to use recursion to get the task done

Version: 1
sum(n){
    if n = 0
    then 0
    else 0 + sum(n-1)
}

The second program will be slower, as there will be n activation record will be created for n function calls. For large value of n, it might cause No Memory Exception.

This problem can be solved by writing the above program differently,

Version: 2
sum(n, res){
   if n = 0
   then res
   else sum(n-1, res+n)
}

Initial call to the function will be, sum(n, 0).

If compared with the first version of the function, the second version of the function does not do anything after it receives the return value of calling function. The later version is called tail recursive function, caller does not do anything after the callee returns, it merely return the value returned by the callee. If a functional programming execution engine detects a tail recursive function, it does not create new activation records for callee functions, callee functions just reuses activation records of the caller.

Source
[0] https://www.coursera.org/learn/programming-languages/lecture/YZic1/tail-recursion