DEV Community

Cover image for Recursion and tail recursion with JavaScript
Kristijan Pajtasev
Kristijan Pajtasev

Posted on

Recursion and tail recursion with JavaScript

Recursion is one of the topics that everyone covers, no matter which programming language you are learning. Probably in the first few classes of any beginner courses. Still, many people struggle with understanding it. This post covers what recursion is, what to watch for when writing a recursive function. Also, there is a section on a tail recursion, a bit more optimized version of recursion.

JavaScript logo

What is recursion?

A commonly used definition of recursion is that it is a self-invoking function. But what does that mean? Usually, you write the function, and then you call it. With recursion, inside of the body of the function, you also call it.

function recursiveFunction() {
    // some code
    recursiveFunction();
}
Enter fullscreen mode Exit fullscreen mode

Looking at snippet about, you might think, this is an infinite loop. What about stack overflow? And you are right. When writing recursion, you need to pay special attention to the end case. But there is a bit more about that one bellow. First, answer to the other question you might ask.

Why and when would you use recursion?

There are different use cases, and everyone has their own opinion. I think they are great when you need to loop something, but you don’t know how many times. Long pull from the server, where you are fetching data as long as there is some. Also, traversing the tree, like HTML nodes and nodes of binary trees.

Breaking recursion

As mentioned above, the end case always needs to be covered. That is the moment when you are stopping recursion. Otherwise, you get an infinite loop. Just for an example, let’s say we need to calculate the factorial of a number. If you don’t know what factorial is, there is a straightforward explanation on the Wikipedia page. Also, for simplicity, let’s assume the argument is always valid value.

function factorial(number) {
    if(number === 1) {
        return number;
    } else {
        return number * factorial(number - 1);
    }
}

factorial(5); // 120
Enter fullscreen mode Exit fullscreen mode

To calculate factorial, you sum all numbers until you reach one. That is also the end case for our recursion, and it is why once we reach value one, we don’t call factorial function anymore.

Tail recursion

Tail recursion is a type of recursive function when the last thing executed is a recursive call. It doesn’t mean much, I know. But simplified, it is a more optimized recursion. So to explain it better, I am going back to the example above. That one is not tail recursion, and it executes in the following way.

factorial(5); // step 1
5 * factorial(4); // step 2
5 * 4 * factorial(3); // step 3
5 * 4 * 3 * factorial(2); // step 4
5 * 4 * 3 * 2 * factorial(1); // step 5
5 * 4 * 3 * 2 * 1; // step 6
Enter fullscreen mode Exit fullscreen mode

As you can see above, first, each factorial call is run. Only then it is multiplying all the number. To convert it to tail recursion, I am changing the function to accept the result as a second parameter.

function tailRecursiveFactorial(number, result = 1) {
    if(number === 1) {
        return result;
    } else {
        return tailRecursiveFactorial(number - 1, result * number);
    }
}

tailRecursiveFactorial(5); // 120
Enter fullscreen mode Exit fullscreen mode

In this case, the function is executing in the following steps.

Step 1: tailRecursiveFactorial(5, 1)
Step 2: tailRecursiveFactorial(4, 5)
Step 3: tailRecursiveFactorial(3, 20)
Step 4: tailRecursiveFactorial(2, 60)
Step 5: tailRecursiveFactorial(1, 120)
Enter fullscreen mode Exit fullscreen mode

This type requires fewer operations and needs fewer items on a stack, which means more performant execution.


For more, you can follow me on Twitter, LinkedIn, GitHub, or Instagram.

Latest comments (7)

Collapse
 
muhammadbasitobaid profile image
muhammadbasitobaid • Edited

For those who are confused with how the performance is improved is this "when a function returns something it is removed from the callstack and js is designed in this way that tail recursion doesn't place new stack frame on to the callstack but it assumes that it is the same function with different arguments and also your accumulated result propagates with each function invocation hence there is no need for other function to wait for successor to return some value that it need to evaluate a mathematical expression, so when we eventually hit the base case the end result is there as well so the result is returned, hope it helps to some extent.

Collapse
 
gilbertq profile image
Ulises Quiñonez

To calculate factorial, you sum all numbers until you reach one.

Not really, you multiply them.

Regards,

Collapse
 
jassehomar profile image
Omar Jasseh

Just by looking, solution two and one uses the same amount of function calls on the stack. Couldn't see the performance benefit here

Collapse
 
hi_iam_chris profile image
Kristijan Pajtasev

Reason for tail recursion is less usage of memory, not less calls. There will be still same number of call, but stack is getting cleared immediately

Collapse
 
ahmedsalahzero profile image
AhmedSalahZero

why would stack be cleared ? the first function does not return any thing yet and it still waiting for the last one to return its values .. am i right ?
sholud the tail recursion and head recursion work exactly the same ???

Collapse
 
webbureaucrat profile image
webbureaucrat

Are you sure the second one uses less room on the stack? I thought JavaScript didn't support tail call recursion optimization.

Collapse
 
hi_iam_chris profile image
Kristijan Pajtasev

You are right, I should make it more clear but I don't want to introduce confusion. Only the newest version of JavaScript and not all browsers support it. I just wanted to illustrate how it optimizes the whole thing, and I did it with JS because it is very easy to read.