The Fibonacci Sequence is┬áthe series of numbers: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 … The next number is found by adding up the two numbers before it. 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


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


2. Dynamic programming solution

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


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


4. Memoization solution

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 animation how Fibonacci recursion works
View animation how Fibonacci memoization works
Numbers and recursions doodle compilation(YouTube)

What are the 4 solutions to find nth Fibonacci number?

From best to worst:
1. Iterative solution, O(n) time, O(1) space.
2. Dynamic programming using an extra array: O(n) time, O(n) space.
3. Dynamic programming using Memoization, O(n) time, O(n) space.
4. Recursion, O(2^n) time, O(n) space.