Recursive Factorial Calculation in JavaScript

Question

function factorial(nb) {
 let tab = [];
 if (nb > 0) {
 tab.push(nb);
 tab = tab.concat(factorial(nb - 1));
 }
 return tab;
}
// Calculate factorial for number 3
const array = factorial(3);
// Calculate the final factorial value by reducing the array
const factorialValue = array.reduce((accumulator, currentValue) => {
 return accumulator * currentValue;
}, 1);
// Output the factorial value
console.log(factorialValue);
// Result 6

The given code defines a function factorial that calculates the factorial of a number. It takes a single parameter nb, representing the number for which the factorial is calculated. The function recursively generates an array tab containing the factorial values by pushing each number from nb down to 1.

After defining the factorial function, the code calls it with the argument 3 and assigns the returned array to the variable array.

Then, the code calculates the final factorial value by using the reduce method on the array. The reduce method multiplies each element in the array together, starting from an initial value of 1. The result is stored in the variable factorialValue.

Finally, the code logs the factorialValue to the console.

Overall, the code accurately calculates the factorial of a given number. However, there are some areas where improvements could be made.

I'm seeking suggestions for improvements in the code to make it more efficient and reduce the execution time. Any tips or alternative solutions would be greatly appreciated.

• greybeard: The GNU Multi-Precision library documentation includes factorial.
• TAHER El Mehdi: I've read it before
• greybeard: Try and document what exactly factorial(nb) does.
• slepic: Are you actually interested in the array? or just the factorialValue?
• TAHER El Mehdi: two gather array and factorialValue

Answer 1

Review

Your code uses too much memory. There is no need to store all the integers of the factorial. You can just keep a running product.

JavaScript and recursion

JavaScript is not a good language to write recursive code in. It has a very limited call stack size. Not only that each call to a function needs a new function context to be created and push to the heap, this makes recursive JS code very memory hungry (and slower than alternatives iterators).

Your function

Your function named factorial does not calculate the factorial, rather it creates an array of factorial divisors. Functions should always do what the name implies.

Storing the array means that the storage complexity of your code is \$O(n)\$ (including the following two examples)

The function below creates an array of factorial divisors using a recursive function.

function factorialArray(n, values = []) {
 if (n > 0) {
 values.push(values.length + 1);
 factorialArray(n - 1, values);
 }
 return values;
}

Or using a non recursive function

function factorialArray(n, values = []) {
 while (n-- > 0) {
 values.push(values.length + 1);
 }
 return values;
}

There are many more ways to create an array of integers from 1 to n, but for this task you don't need any arrays, you just need to keep the running product.

This will reduce the storage complexity to an ideal of \$O(1)\$

Rewrite

The following function calculates the factorial for positive integers.

• Keeping the running product starting at the largest integer and stepping down to the second last value 2 (as there is no need to multiply the last value by 1).

• It uses Math.max to cover the special case of \0ドル! = 1\$

• It uses a while loop to iterate over the divisors, and n (the input argument) is used as the loop counter.

• It has a processing complexity of \$O(n)\$ and storage complexity of \$O(1)\$

• It can calculate the factorial upto 49! at which point it fails due to javascripts Number limitations.

function factorial(n) {
 var result = Math.max(1, n);
 while (n-- > 2) { result *= n; }
 return result;
}

Use BigInt

• JavaScripts Number limits the max usable integer to Number.MAX_SAFE_INTEGER meaning that the largest factorial you can calculate using Number is 49!.

However JavaScript also has BigInt which allows you to calculate factorials upto any value (the only limit is device memory and processing time)

Note that complexity and storage are much greater when using BigInt.

Example using BigInt

function factorial(n) {
 var result = BigInt(Math.max(1, n));
 n = BigInt(n);
 while (n-- > 2n) { result *= n; }
 return result;
}
outputEl.textContent = "957! = " + factorial(957);

code {
 max-width: 100%;
 word-wrap: break-word;
}

<code id="outputEl"></code>

• TAHER El Mehdi: Very Good Answer Thank You
• radarbob: this makes recursive JS code very memory hungry --> Are you saying JS particularly? That's a feature of recursion generally. It is great fun causing a STACK OVERFLOW. Tail-call recursion optimization support takes care of the problem. That optimization is rare among languages as I understand it.
• Blindman67: @radarbob JavaScript does not support Tail-calls (though part of ECMAScript6 standard, agents don't want to break the web (too many pages would hang) so it has no support), without which all recursion is limited by memory (heap or stack). JS has a very small heap ~10,000 calls. Most compiled languages support tail calls using native ASM or indirectly by modifying source . WASM has proposal for new instructions return_call_indirect and return_call that would add native tail calls to the WEB. Tail Calls can optimize much more than just recursive calls.