# What is tail recursion and why is it useful?

Arjun Aravind • 27 July 2021 • 8 min read**Recursion.**The old enemy of computer science students in college and high-school; and the destroyer of interest in any subject relating to data structures or algorithms.

Learning to think about a problem in recursive terms can be a daunting task at first but, once you do it for the first time, you'll soon realise that it's a

**piece of cake**. You'll also realise, funnily enough, that it's the easier way to solve certain kinds of problems!

Today, however, we will be focussing on a special variant of a recursive function,

**the tail recursive function.**

To truly grasp why

**tail recursion**is so useful, we will need to first discuss the basics of two concepts:-

**recursion**itself and the

**computer's call stack**. If you're already good with these, feel free to skip!

What is recursion and is it even necessary?

Briefly speaking, recursion is what we call it when a **function calls itself**in a program.

**Any problem that can be broken down into similar but smaller pieces of itself**is an example of a problem that can be best solved with recursion.

Examples of this are:-

- Calculating the factorial of a number. The factorial of any number N (except 1) can be re-written as (N * factorial of N-1).
- Traversing a tree structure. Every child node in a tree is a tree itself and it's children are also trees.
- Parsing a JSON object. The value for every key in a JSON object can be a JSON object itself.

Now, can all of these problems be solved only by recursion?

To put it simply,

**no**.

**problem which has been solved recursively can be solved**

*Any***iteratively**(that is, using a loop). And the inverse is true as well, any problem which can be solved iteratively can be solved recursively.

**Let's take a simple example.**We shall write two functions, both of which calculate the factorial of a given number. The only difference between the functions is that one will be written

**recursively**and one will be written

**iteratively**.

```
/* RECURSIVE FUNCTION */
function recursiveFactorial (givenNumber) {
if (x == 1) return 1;
else return givenNumber * recursiveFactorial (givenNumber-1);
}
```

```
/* ITERATIVE FUNCTION */
function iterativeFactorial (givenNumber) {
let result = 1;
while (givenNumber > 0) {
result = result * givenNumber;
givenNumber--;
}
return result;
}
```

Both of these functions do the same thing. But can you

**see the difference?**Even in this simple example, the recursive implementation is much more readable and easier to comprehend.

If you're still not convinced, check out this example!

The point is that using recursion

**but it's better, when used for certain problems.**

*isn't necessary*__NOTE:__Not all problems*should*be solved recursively though. Before you solve a problem,If the iterative solution is better, than go ahead with that.*think first.*

Break time?

Alright, let's take a deep breath and take a break. Go drink some water. On to the next section!
What does the call stack of a computer do?

Any task that we perform in our day-to-day lives will consist of a set of **smaller sub-tasks**, which might in-turn consist of

**even smaller sub-tasks.**

When we are doing these smaller tasks,

*what does our brain remember?*It remembers the bigger task, that this sub-task branched off from, so that we can go back to doing that bigger task once we finish doing this sub-task.

Here's an example.

I feel like eating some Pizza right now...

The **right side**shows the tasks and their respective sub-tasks involved in making Pizza. The

**left side**shows what our Brain needs to remember while performing each task.

It's pretty easy to understand, right? When we are cutting vegetables, our brain needs to remember that we are cutting vegetables

**SO THAT**we can cook the sauce

**SO THAT**we can make the pizza.

Similarly, in a program, there will be functions which contain various other function calls, which in-turn, might contain many function calls themselves.So,

**, when the computer is executing**

*just like our brain***smaller function calls inside a function call**, it needs to remember where these function calls originated from so that it can go back to

**that original function once it's done with these smaller function calls.**

Here's the same pizza example but in the form of multiple function calls!

This information about function calls and where they originated from is stored by the computer in a placed called the call stack.

Anything else to know about the call stack?

Yes. A call stack is *limited*by the amount of memory that a computer has. Meaning that if a program has many levels of nested function calls,

*say in the millions*, there is a chance that the

**call stack may run out of memory**and the computer may crash.

You may think,

*but there can't be any program where the functions might consist of a*

**million levels of nested function calls**, right?Well......there is.

**Read on!**

Introducing Tail Recursion!

We shall start with an example. Let's look at our recursive factorial function from earlier.
```
function recursiveFactorial (givenNumber) {
if (x == 1) return 1;
else return givenNumber * recursiveFactorial (givenNumber-1);
}
```

Giving an

**input of 5**, let's trace the program.

- recursiveFactorial(5) will return 5 * recursiveFactorial(4)
- recursiveFactorial(4) will return 4 * recursiveFactorial(3)
- recursiveFactorial(3) will return 3 * recursiveFactorial(2)
- recursiveFactorial(2) will return 2 * recursiveFactorial(1)
- recursiveFactorial(1) will return 1

So,

**recursiveFactorial(5)**will not just have to wait for

**recursiveFactorial(1)**to finish, it will have to wait for the value to be returned by

**recursiveFactorial(2)**,

**recursiveFactorial(3)**and then

**recursiveFactorial(4).**

Remember the call stack? It has to store all these function calls and track the function which called them

**.**

*(in this case, the same function)*So, for an input of 5, we store 4 function calls in the call stack.

**How many function calls are stored when the input is 1,000,000?**Do you remember what may happen when there are a very large number of function calls stored in the call stack?

Now, let's try a different approach to the factorial function to try and prevent this from happening.

```
function recursiveFactorial (givenNumber, result) {
if (x == 1) return result;
else return recursiveFactorial (givenNumber-1, result * givenNumber);
}
```

Notice the difference? We are also passing in the

**product of result and givenNumber**.

Giving an

**input of 5 for givenNumber and 1 for result**, let's trace the program!

- recursiveFactorial(5, 1) will return recursiveFactorial(4, 5)
- recursiveFactorial(4) will return recursiveFactorial(3, 20)
- recursiveFactorial(3) will return recursiveFactorial(2, 60)
- recursiveFactorial(2) will return recursiveFactorial(1, 120)
- recursiveFactorial(1) will return 120

This is amazing! In this case, the factorial is calculated when

**recursiveFactorial(1)**is finished. The value does not need to bubbled up through all those function calls back to

**recursiveFactorial(5)**!

This is what is known as

**tail recursion**. When the recursive function call is the

**action of a procedure and the calling function doesn't need to do**

*final***any further calculation**, it is called a

**tail recursive call.**

In our latest example,

**recursiveFactorial**is a

**function. The value of 120 has already been calculated after**

*tail recursive***recursiveFactorial(1)**.

**AND THIS IS WHERE THE MAGIC HAPPENS**(in some cases, hehe)!

Some language compilers can

*detect*when a function is

**tail-recursive**and prevent the call stack from logging these recursive function calls.

In our case, the computer call stack does not need to keep track of

**recursiveFactorial(2)**,

**recursiveFactorial(3)**and

**recursiveFactorial(4)**because they are all going to return the same thing (120) anyway. So, when

**recursiveFactorial(1)**finishes, the program execution immediately jumps back to

**recursiveFactorial(5)**.

This could also prevent the call stack from exceeding its memory limit, even if the input number is humungously big!

This optimisation technique is called tail call elimination.---------------------

Tail recursion is an important part of

**functional programming languages.**Most of the compilers for those languages have some form of tail call optimisation built in.

---------------------

And that's the end of this!

I hope you guys learnt a lot here about the call stack and tail recursion! Feel free to contact me if you have any criticisms, additions or questions. Cheers!