Problem Statement
The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1.
Given n, calculate F(n).
Solution:
This problem is simple enough. Lets take the iterative approach first. See the code sample below:
public int fib(int n) {
int fib = 0;
// declare the initial variables as 0, 1
int prev = 0;
int cur = 1;
for(int i=0; i<n; i++) {
// fib is addition of previous two numbers
fib = prev + cur;
// update previous two numbers
prev = cur;
cur = fib;
}
return prev;
}You can checkout the code from Github here: Fibonacci Number – First Approach. See the performance of this approach below:
