Tail Recursion

We already know that in recursion, a function recursively calls itself. A recursive call becomes a recursive tail call when the recursive function calls itself at the very end of the function body, i.e., the tail of the function.

Tail Recursive Functions

Tail recursive functions are iterative processes and are the functional form of a loop. They are an optimized version of recursive functions, as they allow the function’s stack frame to be reused.

Stacks are data structures which work like a stack of boxes. Each time a function calls itself, it adds another box or stack frame to the stack. When we add too many boxes to our stack, they fall down. In the same way, when a function makes a large number of recursive calls, the stack overflows.

If the last action of a function consists of calling a function (like a tail recursive function), one stack frame would be sufficient for both functions. Using a lesser number of stacks or a lesser number of stack frames will prevent a stack from overflowing.

A Comparison

Let’s look at the evaluation of both a recursive function and a tail recursive function to better understand how they differ.

A Simple Recursive Call

The factorial function we defined in a previous lesson uses a simple recursive call.