Thursday, January 17, 2013

Optimizing Fibonacci

The first optimization we are going to perform eliminates a method call, as

shown in Listing 1–3. As this implementation is recursive, removing a single

call in the method dramatically reduces the total number of calls. For example,

computeRecursively(30) generated 2,692,537 calls while

computeRecursivelyWithLoop(30) generated “only” 1,346,269. However, the

performance of this method is still not acceptable considering the responsetime

criteria defined above, 100 milliseconds or less, as

computeRecursivelyWithLoop(30) takes about 270 milliseconds to complete.

Listing 1–3. Optimized Recursive Implementation of Fibonacci Series

public class Fibonacci {

public static long computeRecursivelyWithLoop (int n)


if (n > 1) {

long result = 1;

do {

result += computeRecursivelyWithLoop(n-2);


} while (n > 1);

return result;


return n;



No comments:

Post a Comment