In this post, we are going to find n-th Fibonacci number for any given number n. There are 4 implementations. They are iteration, dynamic programming, recursion and memoization.


Table of content


Iterative solution

We use for loop starting from 2. In each iteration, variable sum in the sum of previous two number a and b. When finish, return sum. The time complexity is O(n), space complexity is O(1). It is the best solution.

Java

Javascript

Python

Doodle

fibonacci iteration


Dynamic programming

The basic idea is the same as iteration. In additional, we use an array to save all the result. At the end we return the value with the index of the input number from the array. The time complexity is O(n), space complexity is O(n).

Java

Javascript

Python

Doodle

fibonacci memoization


Recursive solution

The recursion is a simple implementation of the concept, in which each number is the sum of the previous of two number. The base condition is when input is 0 or 1, it return the number itself. It is not efficient. For example, when the input is 4, it calls f(2) twice. So there is overlapping. The time complexity is O(2^n), space complexity is O(n). It is the worst solution.

Java

Javascript

Python

Doodle

fibonacci recursion


Memoization

This method is to overcome the overlapping in recursion using memoization. The solution uses an array to store the partial result. For example, if the result of f(2) is saved, next time the function finds the result in array and returns it. Memoization is one of techniques in called dynamic programming. The time complexity is O(n), space complexity is O(n).

Java

Javascript

Python

Doodle

fibonacci recursion with memoization


Download

Download source code in Java, JavaScript and Python
View how Fibonacci recursion works
View how Fibonacci memoization works
Numbers and recursions doodle compilation(YouTube)

Can you explain Fibonacci numbers in two sentences?

fibonacci sequence

Fibonacci numbers are a sequence of numbers, in which each number is the sum of the two preceding ones. F(0) = 0, F(1) =1, and F(n) = F(n-1) + F(n-2). The first few numbers are: 0, 1, 1, 2, 3, 5, 8, 13, 21…

What is the time complexity of memoization method to find nth Fibonacci number? Is it the best solution?

The time complexity of memoization method is O(n). It is not the best, because its space complexity is O(n). The best is iterative solution. Its time complexity is O(n), its space complexity is O(1).