Find the value of the n-th element in the Fibonacci sequence

One thing I happen to see many times in interviews, coding challenges, or tutorials on recursion is the Fibonacci sequence. It is a coding evergreen. Fibo is a famous series of numbers where each element is the sum of the two previous. The initial condition is: the first element is 1 [sometimes zero], the second element is 1.

The series looks like this: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811… up to infinity.

The question is to write a function that returns the n-th element of this series.

There are several approaches. The first one uses recursion, the second on uses loop.

Here is the code for recursion.

unsigned long long fib(unsigned int n)
{
  if (n <= 1)
    return 1;
  else
    return fib(n - 1) + fib(n - 2);
}

Recursive functions are generally much more problematic because they utilize stack and it can overflow. If you input too big number, the program will crash. Also, they are slower compared to the loop version. On the other hand, it is easier to write it down since it nicely reflects mathematical notation.

This is the code using for loop.

unsigned long long fibo(unsigned int n)
{
  unsigned int first{ 1 };
  unsigned int second{ 1 };
  unsigned int next{};

  if (n <= 1)
    return 1;
  else
  {
    for (size_t i{ 1 }; i < n; ++i)
    {
      next = first + second;
      first = second;
      second = next;
    }
  }
  return next;
}

This function runs faster, handles a much bigger input number as is more effective. Honestly, I always kind of mess it up when I need to write it and it is much faster to look it up - that is why I have put it in here :-)