Software Engineer · Teacher · Author · Vegan

Ah, recursion, one of those intimidating programming topics that make many developers’ heads spin 🤯 . These types of problems can be difficult to conceptualize, especially when you’re under pressure during an interview. I know I’ve felt that before! Well, that’s why I am writing this blog post series on recursion, to help you and me learn it better. As I’ve spent more time learning about it, I’ve come to find it a fascinating topic and appreciate how elegantly you can use it to solve certain types of problems.

Here are the other posts in this series if you haven’t checked those out yet:

- The Obligatory Factorial Function
- Sum an Array of Numbers 3 Ways
- Flattening Arrays
- Palindromes
- Revisiting the Factorial Function with Tail Recursion

In the first post, The Obligatory Factorial Function, we looked at writing a `factorial(n)`

function implemented with recursion. In this post, I wanted to show what that same recursive function would look like if it used tail recursion.

A tail call is a function call that occurs at the end of another function. In the following code, the `bar()`

call is a tail call:

```
function foo() {
return bar();
}
```

Tail recursion occurs when the tail call is recursive. For example, the `foo()`

call is a tail call that is recursive:

```
function foo() {
return foo();
}
```

`factorial(n)`

Without Tail RecursionTo refresh ourselves, here is the implementation of the `factorial`

function from The Obligatory Factorial Function without tail recursion:

```
function factorial(n) {
if (n === 0) {
return 1;
}
return n * factorial(n - 1);
}
```

This function does not have tail recursion because the last line is `n * factorial(n - 1)`

as opposed to `factorial(...)`

.

`factorial(n)`

With Tail RecursionHere is the implementation with tail recursion:

```
function factorial(n, total = 1) {
if (n === 0) {
return total;
}
return factorial(n - 1, n * total);
}
```

When a recursive function uses tail recursion, it *can* be optimized by the JavaScript engine. This optimization is called Tail Call Optimization (TCO). The reason I say *can* is because Tail Call Optimization is part of the JavaScript language specification but it isn’t supported by very many browsers at the time of this writing.

Every time we call a function, a stack frame is created, which is a frame of data that stores information about that function call. This stack frame gets pushed onto the call stack, which is a stack data structure that stores all active function invocations.

When a recursive function has Tail Call Optimization, the call stack won’t continue to grow. To see this in action, visit the following two JSBin links in Safari with the Console open. Make sure your version of Safari is version 13 or higher.

Click on “Run” in the upper right corner and compare the stack traces in each. Notice how in the example without TCO, the stack frames continue to grow? The call stack has a size limitation which depends on the JavaScript engine. If the call stack exceeds that size, then we get the error: `RangeError: Maximum call stack size exceeded`

. The example with TCO ends up using less memory because the call stack doesn’t continue to grow on each recursive call.

If you’d like to learn more about the details of TCO, check out these two posts that I found useful:

*
Disclaimer: Any viewpoints and opinions expressed in this article are those of David Tang and do not reflect those of
my employer or any of my colleagues.
*