# 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.