Tail recursion

Tail recursion is a special case of recursion where the calling function does no more execution after making a recursive call to itself. In other words, a function is named tail recursive if its final expression is a recursive call. The previous recursion examples that we have been introduced to were not tail recursive functions.

To be able to understand tail recursion, we will develop the factorial function that we developed before with the tail recursion technique. Then we will talk about the differences:

func factorial(n: Int, currentFactorial: Int = 1) -> Int { 
    return n == 0 ? currentFactorial : factorial(n: n - 1,
    currentFactorial: currentFactorial * n) 
} 

print(factorial(n: 3)) 

Note that we provide a default argument of 1 for currentFactorial, but this only applies to the very first call of the function. When the factorial function is called recursively, the default argument is overridden with whatever value is passed by the recursive call. We need to have that second argument there because it will hold the current factorial value that we intend on passing to the function.

Let's try to understand how it works and how it is different from the other factorial functions:

factorial(n: 3, currentFactorial: 1) 
return factorial(n: 2, currentFactorial: 1 * 3) // n = 3 
return factorial(n: 1, currentFactorial: 3 * 2) // n = 2 
return 6 // n = 1 

In this function, each time the factorial function is called, a new value for currentFactorial is passed to the function. The function basically updates currentFactorial with each call to itself. We are able to save the current factorial value as it accepts currentFactorial as a parameter.

All of the recursive calls to the factorial, such as factorial(2, 1 * 3), do not actually need to return in order to get the final value. We can see that we actually arrive at the value of 6 before any of the recursive calls actually return.

Therefore, a function is tail-recursive if the final result of the recursive call, in this example 6, is also the final result of the function itself. The non-tail-recursive function is not in its final state in the last function call because all of the recursive calls leading up to the last function call must also return in order to actually come up with the final result.