Tail recursive function in JavaScript

Tail recursive function in JavaScript

·

2 min read

A recursive function is a function that calls itself until it doesn't stop. This technique is called recursion.

Here, function factorial is called in a loop like procedure. Initially, it invokes from outside of the function and invoked inside the same function until the condition false. A recursive function should always have a condition to stop calling itself, otherwise, it will call itself infinitely.

function factorial(n) {
    if (n === 0) {
        return 1; 
    }
    // no proper tail call
    return n * factorial(n - 1); 
}
factorial(3); // 6
`

Max call stack size exceeded error

When a function is invoked, a new stack memory has been created, each runtime environment has a different call stack size. When the code execution reaches the maximum call stack size of the runtime environment, the compiler will throw an error and stop the program begin executing further.

How to avoid max call stack error?

Here comes, tall call optimization plays a role. This is a simple technique, where the same call stack is been used or a new call stack is created after the previous call stack is been garbages. This means recursive function calling is invoked at end of the function sequence execution.

Tail call optimization

'use strict'; 
function factorial(n, total = 1) {
    if (n === 0) {
        return total; 
    }
    // proper tail call
    return factorial(n - 1, n * total); 
}
factorial(3); // 6

From the above code, the factorial function is invoked at end of the function sequence and the compiler doesn't want to prevent stack memory from being garbage.

NOTES

Tail call optimization is a part of ES6 specification. Supporting it isn't a NodeJS thing, it's something the V8 engine that NodeJS uses needs to support. Node 7.10 down to 6.5.0 support this is strict mode only and with the flag "--harmony". But unfortunately, this does not work in Node.JS anymore, as support for tail call optimization has been removed in Node 8. Maybe it will come back😏.

Did you find this article valuable?

Support Rahul by becoming a sponsor. Any amount is appreciated!