Having stumbled upon Project Euler sometime ago and solving the first problem, this disco dancer from the Age of Aquarius thought it was time to tackle problem two, which states:
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
Find the sum of all the even-valued terms in the sequence which do not exceed four million.
Fibonacci, eh? Once again, memories of high school introduction to computing and college CS101 classes came to mind as the classic recursion example stared me in the face. A bit of reading and remembering yielded the following basic equation for solving a Fibonacci sequence (aside from 0 and 1):
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)
That is, the Fibonacci number of some number n is the Fibonacci number of n-1 plus the Fibonacci number of n-2; thus making it a fun exercise in recursion, baby! Yet, while Fibonacci is a great example in recursion, more often than not, the downside to recursion isn’t addressed — that is, recursion is slower than brute force iteration.
While I implemented problem #1 in Groovy, I thought it would be interesting to solve problem #2 in both Java and Groovy as I wanted to get a good feel for the performance differences between solving Fibonacci via recursion and iteration in both languages.
The basic recursive Fibonacci method in Java can be coded like so:
public static long fibonacci(long num){
if(num == 0 || num == 1){
return num;
}else{
return fibonacci(num - 1) + fibonacci(num - 2);
}
}I made the method static as the solution will be executed within a main method for simplicity’s sake. As you can see in the above code, there isn’t anything tricky going on there — just an implementation of the recursive algorithm I elaborated on earlier (and I’ve also handled the 2 base cases — those being 0 and 1).
Interestingly, a close inspection of the problem statement calls for one of my favorite looping constructs (which, sadly, isn’t available in Groovy (yet), by the way): the do-while. That is, the problem essentially states one must perform Fibonacci while the sequence is less than 4,000,000. Accordingly, my solution in Java is as follows:
long fib = 0;
long count = 0;
long answer = 0;
do{
fib = fibonacci(count++);
if(fib % 2 == 0){
answer += fib;
}
}while(fib < 4000000);As you can see, the recursive fibonacci call is made with an incremented counter until such time as the fib variable reaches 4,000,000. Note too, the problem specifies that the answer is the sum of even Fibonacci numbers, hence the modulo operation performed on each value of fib. Note too, that with a do-while there is no need for a bogue break statement, which would otherwise be needed to jump out of the loop (unless you leveraged a normal while loop with the said condition).
Of course, there is another mechanism to solve a Fibonacci sequence — iteration — that is, rather than recursively solving reach sequence, one can just as easily keep a few variables around that hold previous values required for generating a sequence. Thus, the same solution can be achieved in Java like so:
long curr = 0;
long prev = 1;
long answer2 = 0;
long fib2 = 0;
do{
fib2 = (curr + prev);
prev = curr;
curr = fib2;
if(fib2 % 2 == 0){
answer2 += fib2;
}
}while(fib2 < 4000000);Note, the hip code above is essentially the same — all I’ve done in introduced a two variables — curr and prev that facilitate generating a Fibonacci number without recursion.
Having solved the problem, I then went on to see the relative performance issues in Java between the recursive example and iteration-based one. Not surprisingly, running a simple test demonstrated that the recursive algorithm took roughly 580 milliseconds and the iteration-based one took less than 1 millisecond (please rest assured that this was a most un-scientific analysis and in no way should be regarded as reference-able). Thus, in Java, there is a performance hit (albeit slight) for leveraging recursion as opposed to brute force iteration.
The Groovy example is quite similar (most likely due to my laziness and desire to see the relative performance difference between both sets) — in fact, the only difference is the lack of a do-while, which is replaced with a simple while loop. Thus, my recursive loop looks like this:
def fib = 0
def count = 0
def answer = 0
while(fib < 4000000){
fib = fibonacci(count++);
if(fib % 2 == 0){
answer += fib;
}
}And my non-recursive loop like so:
long curr = 0
long prev = 1
long answer2 = 0
long fib2 = 0
while(fib2 < 4000000){
fib2 = (curr + prev)
prev = curr
curr = fib2
if(fib2 % 2 == 0){
answer2 += fib2
}
}Once again, I suppose I could have Groovy-ified the code a lot more and took advantage of the magic of Groovy; however, I wanted the code to be close to the same as Java so as to compare performance results. Thus, running the Groovy example yielded the following un-scientific and therefore un-reference-able data points: the recursive algorithm took approximately 100836 milliseconds (or almost 2 minutes), while the iteration based example took 20 milliseconds.
What’s this all mean, man? Is Groovy slow? Is recursion bogue? The answers are both yes and no — Groovy is going to be a bit slower than normal Java (that difference is becoming narrower and narrower each release though) — in the case of recursion with Fibonacci, Groovy is dramatically slower (most likely due to a lot of reflection magic adding up in terms of call time). Thus, if you find yourself needing deep recursion, Groovy might not fit your needs– all you simply have to do is leverage normal Java. Or you could examine why recursion is called for — you might find that iteration is faster — in which case the relative performance hit between Java and Groovy is slight.
Either way, because it’s my bag, I like to say that for every advantage, there is an equal but opposite disadvantage. That is, with Groovy you gain the advantage of easier coding constructs, no compilation step, etc, which leads to quicker development times; however, you might pay a price in terms of runtime speed. Copasetic developers must weigh these constraints carefully. Do you dig it, man?
