The Fibonacci sequence

The Fibonacci sequence is another problem that we can solve using recursion. It is a series of the numbers 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. The number 2 is found by adding 1 + 1. The number 3 is found by adding 1 + 2, 5 is found by adding 2 + 3, and so on! The Fibonacci sequence can be defined as follows:

1. The Fibonacci number at position 0 is 0.
2. The Fibonacci number at position 1 or 2 is 1.
3. The Fibonacci number at position n (for n > 2) is the Fibonacci of (n - 1) + Fibonacci of (n - 2).

Iterative Fibonacci

We implement the fibonacci function in an iterative way, as follows:

functionfibonacciIterative(n) {
  if (n < 1) return 0;
  if (n <= 2) return 1; 

  let fibNMinus2 = 0;
  let fibNMinus1 = 1;
  let fibN = n;
  for (let i = 2; i <= n; i++) { // n >= 2
    fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
    fibNMinus2 = fibNMinus1;
    fibNMinus1 = fibN;
  }
  return fibN;
}

Recursive Fibonacci

The fibonacci function can be written as follows...