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… Given a number n , you can find n-th Fibonacci number using the following 4 implementations.

Table of Content


Iteration

This is the most efficient implementation. 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.

Java

Javascript

Python

Doodle

fibonacci iteration


Memoization

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.

Java

Javascript

Python

Doodle

fibonacci memoization


Recursion

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 has overlapping. For example, when the input is 4, it calls f(2) twice. The time complexity is 2^n, which is not efficient.

Java

Javascript

Python

Doodle

fibonacci recursion


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. This technique is also called dynamic programming.

Java

Javascript

Python

Doodle

fibonacci recursion with memoization

Download Java, JavaScript and Python code
Fibonacci numbers animated visual