How to find the Nth Fibonacci number
Given an integer number (n <= 40), return Fibonacci number
Note:
F(0) = 0,F(1) = 1,F(n) = F(n-1) + F(n-2) (n >= 2)
Example 1
Input: 5
Output: 5
Example 2
Input: 6
Output: 8
There are several ways how to find the nth Fibonacci number. In this article, we will take a look at two of them: iterative approach and recursive approach. Let's start with the recursive approach.
Using Recursion
Finding the Fibonacci number using recursion is very straightforward. We repeat the Fibonacci formula in the code, and we are done.
public long Fib(int n)
{
if (n <= 1)
{
return n;
}
return Fib(n - 1) + Fib(n - 2);
}
As you see, the code is very simple, there's only one downside - time complexity. This approach has exponential time complexity - O(2^n). As usual, we ask ourselves - "Can we do better?" Oh, yeah, we must do better. This approach is very slow.
The Bottom-Up approach
In the bottom-up dynamic programming approach, we calculate the Fibonacci numbers in order until we reach F(n).
public long Fib(int n)
{
long f0 = 0;
long f1 = 1;
if (n <= 1)
{
return n;
}
for (int i = 2; i < n; i++)
{
long temp = f0 + f1;
f0 = f1;
f1 = temp;
}
return f0 + f1;
}
To calculate F(n) Fibonacci number, we need to store only two previous numbers. We're keeping them in f0 and f1 variables. The time complexity for this approach is O(n), which is significantly better than the recursive one.
