# N-th Fibonacci number

*A classical problem that is used to explain recursion. Recursive solution though is highly inefficient.*

The easiest way to solve the Fibonacci problem is using recursion:

public int fib(int n) {

if (n < 2) {

return 1;

}

return fib(n-1) + fib(n-2);

}

Nice, elegant, but inefficient solution. Each iteration we create 2 new recursive calls which gives us *O(2^n)* running time. And not only it runs slow, it also takes a lot of space: *O(n) *(recursive calls take space. It’s the same as having stack).

More efficient approach would be “bottom-up” one: define an array of size `n+1`

, set `arr[0] = 1`

and `arr[1] = 1`

and calculate `arr[i]`

by adding `arr[i-1]`

to `arr[i-2]`

. Our number is `arr[n]`

. Linear time, linear space.

In fact after some observation you might notice that `arr[i]`

is used only to calculate `arr[i+1]`

and `arr[i+2]`

. So more optimal solution is *O(n)* running time and *O(1)* space.

Recursion: staircase is a modification of a fibonacci number also known as tribonacci numbers. Solution is the same as for fibonacci with the only difference with initial conditions: we fill first 3 numbers in array and summation: we sum three parts instead of 2.