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
|
1 2 3 4 5 6 7 8 9 10 11 12 |
//Iteration, Time O(n), Space space O(1), n is input number public static int fibonacci(int n) { if (n <=1) return n; int a = 0, b = 1, sum = 1; for (int i = 2; i <= n; i++) { sum = a + b; a = b; b = sum; } return sum; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 |
//Iteration, Time O(n), Space space O(1), n is input number function fibonacci(num) { if (num <= 1) return num; var a = 0, b = 1, sum = 1; for (let i = 2; i <= num; i++) { sum = a + b; a = b; b = sum; } return sum; } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 |
#Iteration, Time O(n), Space space O(1), n is input number def fibonacci(num) : if num <= 1: return num a = 0 b = 1 for i in range(2, num+1): sum = a + b a = b b = sum return sum |
Doodle
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
|
1 2 3 4 5 6 7 8 9 10 11 |
//Dynamic programming, Time O(n), Space O(n) public static int fibonacciDP(int n) { if (n <= 1) return n; int[] dp = new int[n+1]; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 |
//Dynamic programming, time O(n), Space O(n) function fibonacciDP(n){ let dp = {}; //itialize the memo dp[0] = 0; dp[1] = 1; for (let i = 2; i <= n; i++){ dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } |
Python
|
1 2 3 4 5 6 |
#Dynamic programming, time O(n), Space O(n) def fibonacciDP(n): dp = [0, 1] # initialize the first two fibonacci numb for i in range(2, n+1): dp.append(dp[i-1] + dp[i-2]) return dp[n] |
Doodle
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
|
1 2 3 4 5 6 |
//Recursion, Time O(2^n), Space O(n) public static int fibonacciRec(int n) { if (n <= 1) return n; return fibonacciRec(n-1) + fibonacciRec(n-2); } |
Javascript
|
1 2 3 4 5 6 |
//Recursion, Time O(2^n), Space O(n) function fibonacciRec(num) { if (num <= 1) return num; return fibonacciRec(num-1) + fibonacciRec(num-2); } |
Python
|
1 2 3 4 5 |
#Recursion, Time O(2^n), Space O(n) def fibonacciRec(num) : if num <= 1: return num return fibonacciRec(num-1) + fibonacciRec(num-2) |
Doodle
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//Recursion + memoization(DP), Time O(n), Space O(n) public static int fibonacciRecMemo(int n) { int[] memo = new int[n+1]; return fibHelper(n, memo); } private static int fibHelper(int n, int[] memo) { if (memo[n] != 0) return memo[n]; if (n <= 1) return n; return memo[n] = fibHelper(n-1, memo) + fibHelper(n-2, memo); } |
Javascript
|
1 2 3 4 5 6 7 8 9 |
//Recursion + memoization(DP), Time O(n), Space O(n) function fibonacciRecMemo(n, memo) { memo = memo || {}; //if no memo, intialize {}, else get values from memo if (n <= 1) return n; if (memo[n]) //check memoization return memo[n]; return memo[n] = fibonacciRecMemo(n-1, memo) + fibonacciRecMemo(n-2, memo); } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 |
memo = [] for i in range(num+1): memo.append(0) #Recursion + memoization(DP), Time O(n), Space O(n) def fibonacciRecMemo(n): if n <= 1: return n if memo[n] != 0: return memo[n] memo[n] = fibonacciRecMemo(n-1) + fibonacciRecMemo(n-2) return memo[n] |
Doodle
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)
What is the time complexity of memoization method to find nth Fibonacci number? How about recursion?
The time complexity of memoization method is O(n). The time of recursion is O(2^n).