Recursive functions with Javascript

Recursion is a powerful programming technique that can be used to solve problems in a more elegant way than traditional looping mechanisms. It relies on the ability of a function to call itself and is often used when dealing with tree-like structures or data sets. In this blog post, we will look at an example of recursion in javascript.

Factorial

The following code snippet defines a recursive function to calculate the factorial of a number. The factorial of a number is defined as the product of all the positive integers less than or equal to that number.

const factorial = (n) => {
  if (n <= 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
};

As we can see in the code, the function will call itself when n is greater than 0, which means that if n equals 0, then we will return 1 because factorial(0) = 1. This is the final exit procedure rule. Without any exit procedure rule, the recursive function could run forever.

If we call this function with an input of 3, it will recursively call itself 3 times to calculate the product of all the numbers from 0 to 3 as the function will start from the exit rule :

• factorial(0)
• factorial(1)
• factorial(2)
• factorial(3)

and return 6 (3 x 2 x 1 x 1).

Fibonacci

Another great example is the Fibonacci sequence.

The Fibonacci sequence is a set of numbers that starts with a 0 followed by a 1, and proceeds based on the rule that each number (called a Fibonacci number) is equal to the sum of the preceding two numbers. So, the sequence goes: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …

We can write that : fib(n) = fib(n-1) + fib(n-2), and we know that:

• fibonacci(0) = 0
• fibonacci(1) = 1
  

With these hypotheses, we can create the JavaScript function as follows:

const fibonacci = (n) => {
  if (n <= 1) {
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
};

Here our recursive loop exit conditions are if n is 1 or 0 and return itself.

console.log(fibonacci(5)) will display 5, and console.log(fibonacci(10)) will display 55.

It works !!!

Now … let’s display console.log(fibonacci(50))

Well if you execute the code, you can see that you have to wait some time to get the result.

For each calculation, the function must calculate the 2 previous terms, and if you imagine the calculation tree, it is massive.

Dynamic programming

To solve this performance issue, let’s introduce some dynamic programming.

Dynamic programming is a method for solving complex problems by breaking them down into smaller, simpler subproblems. It is typically used to solve optimization problems, such as finding the shortest path between two points or determining the most efficient way to schedule a set of tasks.

Here we will save calculation results in an object to avoid duplicate calculation, and increase the performance of the function.

First we will define an object that contains the calculation memory :

const fibonacci = (n, memo = {}) => {
  if (n <= 1) {
    return n;
  } else {
    return fibonacci(n - 1, memo) + fibonacci(n - 2, memo);;
  }
};

And we will store the calculation result at the n index, return it, and include the memo object in the recursive call to keep this results dictionary:

const fibonacci = (n, memo = {}) => {
  if (n <= 1) {
    return n;
  } else {
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
  }
};

At last, we will first check if a result already exists, ad if yes return it before doing any calculation:

const fibonacci = (n, memo = {}) => {
  if (memo[n]) {
    return memo[n];
  }

  if (n <= 1) {
    return n;
  } else {
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
  }
};

Now console.log(fibonacci(50)) will only take seconds to display the result, and the same for console.log(fibonacci(200))

Conclusion

We have seen how recursion works with javascript, and we also introduced dynamic programming to increase performance.

These techniques can be really useful in some situations, and I hope this article will help you to understand recursion a little bit better.

What can you do to help me?

Please don’t hesitate to:

• Like the article
• Follow me
• Leave a comment and express your opinion.
  

Happy coding!