This week's book giveaway is in the Servlets forum. We're giving away four copies of Murach's Java Servlets and JSP and have Joel Murach on-line! See this thread for details.

Hi I'm back again after a small hiatus and of course I have a problem. My code calculates the fibonacci number from 1 to 'maxnumber' I am using recursion and threads (the class these methods are in implement Runnable).

The problem is that if my loop (while) runs until the number == maxNumber and then it NEVER increments, but it continues to add numbers. Here's some sample output. (Using 5 as the maxNumber)

It looks like that's because of the recursion, not the threads. Each call to "calculateFibonacci" has its own copy of "number" which is never incremented. Your "while" is behaving more like an "if". I tried to "fix" your code fragment but it seemed to have so many misunderstandings that it was easier for me to start from scratch. Here's some code demonstrating two ways to generate a Fibonacci number; the iterative (quick) way, and the recursive (simple) way. To run it just enter "java Fibber n", where n is the Fibonacci number you wish to generate, or just "java Fibber" to use the default of 5. Bear in mind that the recursive algorithm can take a long time for large numbers. I hope these will give you some ideas.

Note: Your example code wouldn't compile. I assume there's more to your real program than this little fragment, but things like a lower case 's' in "system.out" seem to show that this was not the actual code that you ran. It's always more helpful if you can cut-n-paste some actual code to help avoid typing mistakes.

Hi Frank Thanks for taking a look at this. I tried out your code and maybe I misunderstood what a Fibonacci number is but your calculation don't seem to work. I do, however, want to mention that my question was more so I would understand recursion as opposed to actually generating a Fibonacci Number. (P.S. I am trying to test out our app and I 'need' something that will take a long time to process. Hence my choice for Fibonacci (or even Prime generation).) What I am now more curious about is why the line where I perfom the while loop does not work properly? In the method where I call the while statement I print out the value of number and I also added priting out the value of maxNumber and they do show up as equal but the loop continues without incrementing number Very confusing. Oh yeah, please fell free to move this to another 'thread' if you feel it's getting off topic. Thanks.

Frank Carver
Sheriff

Joined: Jan 07, 1999
Posts: 6920

posted

0

OK. Just for interest, a Fibonacci series is a sequence of numbers such that each number is the sum of the two preceding numbers. eg. 0 1 1 2 3 5 8 13 21 ... Fibonacci series' and variants are sometimes found in biological systems. The sequence your code generates is sometimes known as Pascal's series, or the triangular numbers. Each number is the sum of the preceding number and the next integer eg. 0 1 3 6 10 15 21 28 36 ... As for why your recursion isn't working. It's because at each "level" of the recursion, the value of "number" never changes. Consider your code, ignoring the "println"s: <pre> public static int calculateFibonacci(int number) { while(number <= maxNumber) { runningTotal += calculateFibonacci(number+1); } return runningTotal; } </pre> In your while loop "number" never changes, so you will never exit from the loop. The effect you are seeing is best described by working through the code for a (small) max number. let's use 3. For brevity, I'll abbreviate calculateFibonnacci to cf. <pre> code total run calls cf(0) 0 while 0 < 3 call cf(1) 1 while 1 < 3 call cf(2) 3 while 2 < 3 call cf(3) 6 while 3 < 3 no, so return while 2 < 3 call cf(3) 10 while 3 < 3 no, so return while 2 < 3 call cf(3) 14 while 3 < 3 no, so return while 2 < 3 call cf(3) 18 while 3 < 3 no, so return

... </pre> Forget about the recursion for the moment, and ask yourself why you would ever want to write a while loop where the variable being tested never changes. Does that help?

John Bateman
Ranch Hand

Joined: Mar 09, 2000
Posts: 320

posted

0

Hi Ahhhhhhhhhhhhhhhh he says with a big grin on his face I learned two things there... 1> The proper definition of Fibonacci.. I was actually trying to add up the numbers up to and incliding the 'passed' value. I.E> If it was 5 doing 1+2+3+4+5 = 15. 2> I was assuming that since I called the function again using cf(number+1) that the while loop would now re-read the number (while jumping out of the old loop due to new method call). I now realise I should have used an IF instead of a WHILE there. (and incremented the number inside the method itself). Thank you for the explanation and the example. It's cleared up alot of things for me now. Appreciate it.

[This message has been edited by John Bateman (edited June 13, 2000).]

This is the problem with programmers now-a-days. No one thinks about the problem. I know this is an example to learn, but I see all of the time. If someone needed a fibonacci number in real life, they would go and calculate it this way. Does anyone care that you do NOT need recursion OR a loop to calculate a single fibonacci number? People never go through computer science training, but instead just learn the languages and get "certified". import java.lang.*; public class Fib { final static double k=Math.sqrt(5), j=(1+k)/2.0; static long fib(int n) { return Math.round(Math.pow(j,n+1)/k); } }