## Nth Fibonacci number

Write a method to generate the $n$th Fibonacci number.

My initial thoughts:

• Base case: F(0) = 0, F(1) = 1.
• Recursion: F(n) = F(n-1) + F(n-2)

My initial codes:

```	public static int Fibonacci(int n) {
if (n < 0)
return -1;
if (n == 0)
return 0;
if (n == 1)
return 1;
return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Solution:

Recursive solution:
public static int fibo(int n) {
if (n == 0) {
return 0; // f(0) = 0
} else if (n == 1) {
return 1; // f(1) = 1
} else if (n > 1) {
return fibo(n - 1) + fibo(n - 2); // f(n) = f(n—1) + f(n-2)
} else {
return -1; // Error condition
}
}

Handles more error conditions than mine.
Time complexity: $O(2^{n})$; Space complexity $O(n)$ considering the function call stack.

Iterative Solution:
public static int IterativeFibo(int n) {
if (n < 0)
return -1; // Error condition.
if (n == 0)
return 0;
int a = 1, b = 1;
for (int i = 3; i <= n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}

Time complexity: $O(n)$; Space complexity $O(1)$.

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5b27ff224ea1b', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5b27ff224ea49',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5b27ff224ea4b',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});