Tail Recursion

In this lesson, you will be introduced to Scala's preferred form of recursion: 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.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy