The Fibonacci sequence begins with Fibonacci(0) = 0 and Fibonacci(1)=1 as its respective first and second terms. After these first two elements, each subsequent element is equal to the sum of the previous two elements.
Here is the basic information you need to calculate Fibonacci(n):
- Fibonacci(0) = 0
- Fibonacci(1) = 1
- Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)
Task
Given n, complete the fibonacci function so it returns Fibonacci(n).
Input Format
Nth number
Output Format
Fibonacci() Nth number.
Sample Input
3
Sample Output
2
Explanation
Consider the Fibonacci sequence:
We want to know the value of Fibonacci(3). If we look at the sequence above,Fibonacci(3) evaluates to 2. Thus, we print 2 as our answer.
public static int Fibonacci(int n)
{
if (n == 0) return 0;
else if (n == 1) return 1;
else
{
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
This is alot more efficient since you are not creating stack frames that are pushed onto the stack, but rather keeping growth on the heap which is much bigger than the heap. Stack frames also have overhead like stack pointers that point to the next and previous frames.
private static long Fib(int n)
{
Dictionary cache = new Dictionary();
cache[0] = 1;
cache[1] = 1;
while (cache.Count < n) { cache[cache.Count] = cache[cache.Count – 1] + cache[cache.Count – 2]; } return cache[n – 1]; }