Question

Looking at the recursive formula we can design a simple program use pseudocode. Fibonacci(n): if (n == 0) return 0; if (n == 1) return 1; return Fibonacci (n-1) + Fibonacci(n-2).

Discuss any issues you find with your program and what reasoning there may be.

Answer 1

The psedudo code is present in the code blocks below. This is an iterative approach to solve this. Similarly the formula can be directly mapped to a recursive solution as well.

getFibonacci(int n) : method  {

define F: array to store fibonacci.
// initialise starting values.
F[0] = 0, F[1] = 1;

n: int storing the max fibonacci number to get.
iterate i from 2 to n:
  F[i] = F[i-1] + F[i-2];


return F[i];
}

The above code is for a method that returns the nth fibonacci number. The only place where this could create a problem is when we have to redo the same process of calculating the fibonacci number again. To mitigate that issue, we could store fibonacci numbers to its max value and then can just refere it next time instead of calculating it.