Recursive Fibonacci in Java with Memoization
Introduction
This article first explains how to implement recursive fibonacci algorithm in java, and follows it up with an enhanced algorithm implementation of recursive fibonacci in java with memoization.
What is Fibonacci Sequence
Fibonacci is the sequence of numbers which are governed by the recurrence relation - "F(n)=F(n-1)+F(n-2)".
The first 2 numbers numbers in the sequence are 0,1 . The Fibonacci sequence, based on the recurrence relation given above, goes like this - 0,1,1,2,3,5,8,13,21 and so on... Recursive Fibonacci Implementation Given below is a recursive java program which generates numbers in the Fibonacci sequence -
Output for the above program
In the above program the Fibonacci calculation is done in the method fibonacci() which takes as input a single parameter of type long (long n), and returns the number at the nth position in the Fibonacci series. As you must have noticed, the method is recursive in nature and calls itself twice for computing Fibonacci numbers at the position 'n' and 'n-1'. It then adds up these 2 values which is in line with the recurrence relation describing Fibonacci numbers.
The program also computes and prints out the time taken in determining this number. In this case (n=25), time taken was 10 milliseconds. Lets run this program for n > 25 and see how much time it takes. For n=30 (17 ms), n=35 (105 ms), n=40 (1023 ms), n=45(12083 ms), n=46 (17872 ms), n=48 (30889 ms). As you can see, the time taken is increasing at an alarming rate because the number of recursive calls are increasing at a very high rate with every increase in the value of n.
This deterioration in performance can be improved by an optimization technique called Memoization. In Memoization the results of expensive function calls, i.e. functions which take a lot of time, are cached on their first run. These cached values are then re-used when the function is called again with the same inputs. Recursive Fibonacci Implementation using Memoization Given below is a recursive java program for Fibonacci generation which utilizes the concept of memoization to improve its performance -
Output for the above program
As you can see in the above program, the value of every fibonacci number at position 'n' is being stored in an array called 'fibArray' at position 'n'. At the first instance of calling fibonacci(n), the result is also stored in fibArray[n]. Next time when this value is needed again then instead of calculating this value again recursively, the program simply picks it up from the array. It comes to know whether a value is cached or not simply by checking if the value is not zero.
Using memoization, the performance improves drastically. I checked for n=30, n=50, n=80, n=120 and so on. The time taken kept coming as 0 ms. It was around n=150 that the time taken increased to 1 ms. Compared to time taken without Memoization, this is a very good.
Note: Please remember to increase the fibArray[] initialization size(in the program above) to make it greater than or equal to 'n' when calculating 'fibonacci(n)'.
The first 2 numbers numbers in the sequence are 0,1 . The Fibonacci sequence, based on the recurrence relation given above, goes like this - 0,1,1,2,3,5,8,13,21 and so on... Recursive Fibonacci Implementation Given below is a recursive java program which generates numbers in the Fibonacci sequence -
Recursive Fibonacci Implementation
package com.javabrahman.commonprograms;
public class Fibonacci {
public static long fibonacci(long n) {
if(n==0 ){
return 0;
}else if(n==1){
return 1;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
public static void main(String args[]) {
long preTime=System.currentTimeMillis();
System.out.println("Value of 25th number in fibonacci series->"+fibonacci(25));
long postTime=System.currentTimeMillis();
System.out.println("Time taken to compute in milliseconds->"+(postTime-preTime));
}
}Value of 25th number in Fibonacci series->121393 Time taken to compute in milliseconds->10
In the above program the Fibonacci calculation is done in the method fibonacci() which takes as input a single parameter of type long (long n), and returns the number at the nth position in the Fibonacci series. As you must have noticed, the method is recursive in nature and calls itself twice for computing Fibonacci numbers at the position 'n' and 'n-1'. It then adds up these 2 values which is in line with the recurrence relation describing Fibonacci numbers.
The program also computes and prints out the time taken in determining this number. In this case (n=25), time taken was 10 milliseconds. Lets run this program for n > 25 and see how much time it takes. For n=30 (17 ms), n=35 (105 ms), n=40 (1023 ms), n=45(12083 ms), n=46 (17872 ms), n=48 (30889 ms). As you can see, the time taken is increasing at an alarming rate because the number of recursive calls are increasing at a very high rate with every increase in the value of n.
This deterioration in performance can be improved by an optimization technique called Memoization. In Memoization the results of expensive function calls, i.e. functions which take a lot of time, are cached on their first run. These cached values are then re-used when the function is called again with the same inputs. Recursive Fibonacci Implementation using Memoization Given below is a recursive java program for Fibonacci generation which utilizes the concept of memoization to improve its performance -
Recursive Fibonacci Implementation using Memoization
package com.javabrahman.commonprograms;
public class FibonacciWithMemoization {
public static long fibArray[]=new long[26];
public static long fibonacci(long n){
long fibValue=0;
if(n==0 ){
return 0;
}else if(n==1){
return 1;
}else if(fibArray[(int)n]!=0){
return fibArray[(int)n];
}else{
fibValue=fibonacci(n-1)+fibonacci(n-2);
fibArray[(int) n]=fibValue;
return fibValue;
}
}
public static void main(String args[]){
fibArray[0]=1;
fibArray[1]=1;
long preTime=System.currentTimeMillis();
System.out.println("Value of 25th number in Fibonacci series->"+fibonacci(25));
long postTime=System.currentTimeMillis();
System.out.println("Time taken to compute in milliseconds->"+(postTime-preTime));
}
}Value of 25th number in Fibonacci series->121393 Time taken to compute in milliseconds->0
As you can see in the above program, the value of every fibonacci number at position 'n' is being stored in an array called 'fibArray' at position 'n'. At the first instance of calling fibonacci(n), the result is also stored in fibArray[n]. Next time when this value is needed again then instead of calculating this value again recursively, the program simply picks it up from the array. It comes to know whether a value is cached or not simply by checking if the value is not zero.
Using memoization, the performance improves drastically. I checked for n=30, n=50, n=80, n=120 and so on. The time taken kept coming as 0 ms. It was around n=150 that the time taken increased to 1 ms. Compared to time taken without Memoization, this is a very good.
Note: Please remember to increase the fibArray[] initialization size(in the program above) to make it greater than or equal to 'n' when calculating 'fibonacci(n)'.