I wrote some time ago about recursion and dynamic programming to create a function that will calculate the result of a given 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, …

The rule is : fib(n) = fib(n-1) + fib(n-2).

The Fibonacci sequence is very often used to illustrate recursion, but we could also consider doing this function using loops.

Recursive approach with dynamic programming

With recursion, the Fibonacci function will call itself until encountering the exit rule to produce the result.

To improve the execution process, we can include memoization to store the results and avoid calculating a result that was already calculated.

The function code will look like this :

const fibonacci = (n, memo = {}) => {
  if (memo[n]) { //check if result exist in the memo object
    return memo[n];
  };

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

Looping approach

Also, we can consider using a function based on a loop to calculate the result.

We will set the base cases fib(0) and fib(1) and we will loop each step to calculate the value and return the last sum.

Here is also the javascript code :

const fibonacciSimple = (n) => {
  if (n > 1) {
    var a = 0;
    var b = 1;
    var c = 0;

    for (let index = 2; index < n; index++) {
      c = a + b;
      a = b;
      b = c;
    };

    return a + b;
  } else {
    return n;
  };
};

So … ?

The recursive approach means that each time we call the function it will try to solve the problem in multiple sub-problems by calling itself again until the exit condition is met. The looping approach will iterate and return the calculation for each loop until it reaches the end of the process.

But of course, the result produced by these 2 functions are identical.

The question

I asked then myself, why for some problems, and here, for example, people focus on recursion and don’t just solve it with simple loops.

One explanation I’ve heard it’s that is much more elegant 🙂 And well, I have to agree here.

But I wanted to go deeper and understand if there were some technical considerations.

The test

I wrote both functions in a file and added an execution time measurement using performance.now() :

const fibonacci = (n, memo = {}) => {
  if (memo[n]) {
    //check if result exist in the memo object
    return memo[n];
  }

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

const fibonacciSimple = (n) => {
  if (n > 1) {
    var a = 0;
    var b = 1;
    var c = 0;

    for (let index = 2; index < n; index++) {
      //looping to calculate each fibonacci step
      c = a + b;
      a = b;
      b = c;
    }

    return a + b; //return last sum
  } else {
    return n; //exit condition
  }
};

const myNumber = 10; // my test value

var startTime1 = performance.now();
console.log('fibsimple ' + myNumber, fibonacciSimple(myNumber));
var endTime1 = performance.now();
console.log(
  `Call to fibonacciSimple took ${endTime1 - startTime1} milliseconds`
);

var startTime2 = performance.now();
console.log('fib ' + myNumber, fibonacci(myNumber));
var endTime2 = performance.now();
console.log(`Call to fibonacci took ${endTime2 - startTime2} milliseconds`);

Test 1

Call both functions to calculate fib(10)

Test 2

Call both functions to calculate fib(100)

Test 3

Call both functions to calculate fib(1000)

Test 4

Call both functions to calculate fib(5000)

As we can see, in each test the recursive method is much more performant, and its execution time is faster.

One more test

Let’s call both functions to calculate fib(50000)

In this case we crossed the limit of the recursion stack and the calculation was not possible here, although the looping based function did the job.

Conclusion

As very often there is no black-or-white answer to a technical coding question. We could see that recursion can be more performant compared to a simpler algorithm. But also we could see that the limits can be reached quicker with a recursive function, and that the simpler algorithm will do the calculation, maybe slower, but will come to the end.

These are the tricky parts that make me love the technology!

Even if everything is (today) based on 0 and 1, there are plenty of shades when it comes to create something.

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!