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.