John Bateman

Ranch Hand

Posts: 320

posted 16 years ago

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)

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)

*SOURCE CODE* should be *SURROUNDED* by "code" tags.

Frank Carver

Sheriff

Posts: 6920

posted 16 years ago

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

I hope these will give you some ideas.

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.*
John Bateman

Ranch Hand

Posts: 320

posted 16 years ago

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

Very confusing.

Oh yeah, please fell free to move this to another 'thread' if you feel it's getting off topic.

Thanks.

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.

*SOURCE CODE* should be *SURROUNDED* by "code" tags.

Frank Carver

Sheriff

Posts: 6920

posted 16 years ago

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?

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

Posts: 320

posted 16 years ago

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).]

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).]

*SOURCE CODE* should be *SURROUNDED* by "code" tags.

Pete Pan

Ranch Hand

Posts: 44

posted 16 years ago

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);

}

}

proof left for the reader

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);

}

}

proof left for the reader