DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Refcards Trend Reports Events Over 2 million developers have joined DZone. Join Today! Thanks for visiting DZone today,
Edit Profile Manage Email Subscriptions Moderation Admin Console How to Post to DZone Article Submission Guidelines
View Profile
Sign Out
Refcards
Trend Reports
Events
Zones
Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
  1. DZone
  2. Data Engineering
  3. AI/ML
  4. Memoized Fibonacci Numbers with Java 8

Memoized Fibonacci Numbers with Java 8

Edwin Dalorzo user avatar by
Edwin Dalorzo
·
May. 12, 13 · Interview
Like (0)
Save
Tweet
Share
17.01K Views

Join the DZone community and get the full member experience.

Join For Free

since today is fibonacci day , i decided that it would be interesting to publish something related to it.

i believe one of the first algorithms we all see when learning non-linear recursion is that of calculating a fibonacci number. i found a great explanation on the subject in the book structure and interpretation of computer programs [sic] and i dedicated some time to playing with the fibonacci algorithm just for fun. while doing so i found an interesting way to improve the classical recursive algorithm by using one of the new methods (added in java 8) in the map interface and which i used here to implement a form of memoization .

classical recursive fibonacci

in the classical definition of fibonacci we learn that:

fib(n) = \left\{ \begin{array}{ll} 0 & \mbox{if n=0}\\1 & \mbox{if n=1}\\fibn(n-1)+fib(n-2) & \mbox{otherwise} \end{array} \right.

we program this very easily in java:

public static long fibonacci(int x) {
if(x==0 || x==1)
return x;
return fibonacci(x-1) + fibonacci(x-2);
}

now the problem with this algorithm is that, with the exception of the base case, we recursively invoke our function twice and interestingly one of the branches recalculates part of other branch every time we invoke the function. consider the following image (taken from sic) that represents an invocation to fibonacci(5) .

clearly the branch to the right is redoing all the work already done during the recursive process carried out by the left branch. can you see how many times fibonacci(2) was calculated? the problem gets worse as the function argument gets bigger. in fact this problem is so serious that the calculation of a small argument like fibonacci(50) might take quite a long time.

memoized recursive fibonacci

however, there is a way to improve the performance of the original recursive algorithm (i mean without having to resort to a linear-time algorithm using, for instance, binet’s formula ).

the serious problem we have in the original algorithm is that we do too much rework. so, we could alleviate the problem by using memoization , in other words by providing a mechanism to avoid repeated calculations by caching results in a lookup table that can later be used to retrieve the values of already processed arguments.

in java we could try to store the fibonacci numbers in a hast table or map. in the case of the left branch we’ll have to run the entire recursive process to obtain the corresponding fibonacci sequence values, but as we find them, we update the hash table with the results obtained. this way, the right branches will only perform a table lookup and the corresponding value will be retrieved  from the hash table and not through a recursive calculation again.

some of the new methods in the class map , in java 8, simplify a lot the writing of such algorithm, particularly the method computeifabsent(key, function) . where the key would be the number for which we would like to look up the corresponding fibonacci number and the function would be a lambda expression capable of triggering the recursive calculation if the corresponding value is not already present in the map.

so, we can start by defining a map and putting the values in it for the base cases, namely, fibonnaci(0) and fibonacci(1) :

private static map<integer,long> memo = new hashmap<>();
static {
memo.put(0,0l); //fibonacci(0)
memo.put(1,1l); //fibonacci(1)
}


and for the inductive step all we have to do is redefine our fibonacci function as follows:

public static long fibonacci(int x) {
return memo.computeifabsent(x, n -> fibonacci(n-1) + fibonacci(n-2));
}

as you can see, the method computeifabsent will use the provided lambda expression to calculate the fibonacci number when the number is not present in the map, this recursive process will be triggered entirely for the left branch, but the right branch will use the momoized values. this represents a significant improvement.

based on my subjective observation, this improved recursive version was outstandingly faster for a discrete number like fibonacci(70) . with this algorithm we can safely calculate up to fibonacci(92) without running into long overflow. even better, to be sure that our algorithm would never cause overflows without letting the user know we could also use one of the new methods in java 8 added to the math class and which throws an arithmeticexception when overflow occurs. so we could change our code as follows:

public static long fibonacci(int x) {
return memo.computeifabsent(x, n -> math.addexact(fibonacci(n-1),
fibonacci(n-2)));
}

this method would start failing for fibonacci(93) . if we need to go over 92 we would have to use biginteger in our algorithm, instead of just long.

notice that the memozied example uses mutations, therefore, in order to use this code in a multithreaded environment we would first need to add some form of synchronization to the proposed code, or use a different map implementation, perhaps a concurrenthashmap , which evidently, may impact performance as well. arguably, this would still be better than the original recursive algorithm.

Java (programming language) Algorithm Branch (computer science)

Published at DZone with permission of Edwin Dalorzo. See the original article here.

Opinions expressed by DZone contributors are their own.

Popular on DZone

  • How Observability Is Redefining Developer Roles
  • Iptables Basic Commands for Novice
  • Web Application Architecture: The Latest Guide
  • Understanding gRPC Concepts, Use Cases, and Best Practices

Comments

Partner Resources

X

ABOUT US

  • About DZone
  • Send feedback
  • Careers
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 600 Park Offices Drive
  • Suite 300
  • Durham, NC 27709
  • support@dzone.com
  • +1 (919) 678-0300

Let's be friends: