Algorithmic Problem Solving: Preparing for a Coding Interview/

...

/

Solution: Fibonacci Number

Solution: Fibonacci Number

Solutions for the Fibonacci Number Problem.

We'll cover the following...

Solution 1: Recursive algorithm

Below, we show a straightforward implementation of the recursive pseudocode. It contains a debug instruction that prints what is currently computed. We then try to compute F7F_7 using this code.

Code

Click the “Run” button to see the output.

#include <iostream>
int fibonacci(int n) {
    if (n <= 1)
        return n; // Returing n when n is less than or equal to 1
    else{
      std::cout << "Computing F" << n << " recursively..." << std::endl; // comment this line before testing
      return fibonacci(n - 1) + fibonacci(n - 2); // recursively calculating Fibonacci number 
    }
}
int main() {
  std::cout << fibonacci(7);
  return 0;
}
Recursive algorithm

As we see, the code produces the right result, 13, but many computations are repeated! If we run this code to compute F150F_{150}, the sun might die before our computer returns the result!

Stop and think: How would you compute F7F_7 by hand?

Solution 2: Iterative algorithm

Most probably, to compute F7F_7 by hand, we would write something like this on a piece of paper:

It makes perfect sense to ask a computer to compute FnF_n in the same iterative manner:

 Fibonacci(n)Fibonacci(n) ...

Access this course and 1400+ top-rated courses and projects.