Monday, December 2, 2019

JavaScript Recursive Factorial Algorithm

This blog post is about "Recursive Function in JavaScript". The ability for a function to call it self is know as 'Recursion'.

A recursive function has two parts namely: the base case (which gets called when the recursion is satisfied needs to terminate) and the recursive case (which continue to call the function they are in until the base case condition is satisfied)

Recursion is particularly useful for divide and conquer problems. A simple problem that naturally best solved by recursive solution is 'calculating factorials'.

The recursive factorial algorithm defines two cases:
~ the base case when x is zero, and
~ the recursive case when x is greater than zero.

Factorial of a number 'x' is the product of all positive integers less than or equal to the number 'x'. For example the factorial of 6 is: 1 x 2 x 3 x 4 x 5 x 6 = 720

The implementation is as follow:-

function myRecur_factorial(x){
    if (x == 1){
        return x; // This is the: Base Case
    } else{
        return(x * myRecur_factorial(x-1)) // This is the: Recursive Case

x = 6

console.log(`The factorial of ${x} is: ` + myRecur_factorial(x))

Here is a non-recursive approach to writing factorial of a number in JavaScript.

This make use of 'range function' and the 'for loop'. Because JavaScript has built-in range function, we will define one as follow..

function range(start, end) {
    return (new Array(end - start + 1)).fill(undefined).map((_, i) => i + start);

number = 6
factorial = 1

for (i of range(1, number)) {
    factorial = factorial * i;

console.log(`The factorial value for the ${number} is: ` + factorial);

Recursion and Iteration are somewhat similar and often confused by programmers because they both repeat a series of operations. It is mostly not clear if recursion or iteration is a better solution to a particular problem. The following table highlights some differences between recursion and iteration:

When the base case is reached, it terminates
It terminates when a defined condition is met
Space in memory is required to store each  recursive call
Iteration is not stored in memory
Stack Overflow Error occurs when a recursion is  infinite
Infinite iteration will not return error

Another example of recursion is when we used a recursive approach to generating all the possible permutations of a given string, X, of a given length Y:

No comments:

Post a Comment