Originally posted by kelvin cheung: hm.. it never goes back to the println in the constructor

Look at the first case you handle in your fibonacci method.

P.S. Remember that f(n) = f(n-1) + f(n-2), f(1) = 1 and f(0)=0. You code has another mistake in that respect.

Also note that there is a more efficient way to do this, which you might get extra credit for.

One final thing I thought I'd mention. I don't know if your assignment specifies the maximum item in the sequence your program must be able to calculate, but using int, you will only get to the high forties. Using long, you will be able to calculate to the low ninties. If you have to calculate higher than this, you would have to look into more complex data types that can store the massive numbers. [ March 15, 2005: Message edited by: Horatio Westock ] [ March 15, 2005: Message edited by: Horatio Westock ]

i have made another verison of the recursion code:

it does correctly calculates the Fibonacci number, but i dont understand the output. can someone help me to analyze a small part of it so i can understand?

method argument higher than 2: 11 method argument higher than 2: 9 method argument higher than 2: 7 method argument higher than 2: 5 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 6 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 5 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 8 method argument higher than 2: 6 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 5 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 7 method argument higher than 2: 5 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 6 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 5 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 10 method argument higher than 2: 8 method argument higher than 2: 6 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 5 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 7 method argument higher than 2: 5 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 6 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 5 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 9 method argument higher than 2: 7 method argument higher than 2: 5 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 6 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 5 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 8 method argument higher than 2: 6 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 5 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 7 method argument higher than 2: 5 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 6 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 5 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 method argument higher than 2: 4 is less or equals 2: 2 return 1 method argument higher than 2: 3 is less or equals 2: 1 return 1 is less or equals 2: 2 return 1 Fibonacci(11) = 89 Used milliseconds = 1110915324593

Horatio Westock
Ranch Hand

Joined: Feb 23, 2005
Posts: 221

posted

0

Half of my message disappeared I think this is what was missing:

Have you tried f(0)? I don't think you will get the correct answer!

You need to consider the cases your fibonacci method must cater for.

Firstly, f(0)=0, you must detect this and return 0.

Second, f(1)=1, you must detect this and return 1.

Finally, to calculate other members of the series you use f(n) = f(n-1) + f(n-2). Your program is using recursion correctly to do this.

Below is a workthrough of how fibonacci works, and how it relates to your program:

So this is how the sequence builds up. In you program, the first line in each of the workings above is the recursive call: fibonacci(n-1)+fibonacci(n-2). Each of those methods will in turn make a recursive call, until their value is either 0 or 1, in which case the method will return 0 or 1 respectively.

Once you have fixed your method to return 0 for a parameter value of 0, and 1 for a parameter value of 1, I suggest you test it with smaller numbers. Calculating f(11) requires quite a few recursions which makes it hard to see what is happening.

Good luck, and once you have grasped this, if you are interested in the more efficient method I mentioned, then just ask

[ March 15, 2005: Message edited by: Horatio Westock ] [ March 15, 2005: Message edited by: Horatio Westock ]

kelvin cheung
Ranch Hand

Joined: Mar 27, 2004
Posts: 120

posted

0

hello,

thank you for your help! it was useful.

i added these lines:

and i have tested the fib(0). it works now i think ^^

1. Instead of writing to standard out when n < 0, throw an IllegalArgumentException, with the message being the string you are now writing to System.out.

2. You only need to check the n=0 and n=1 cases (rather than n <= 2). n=2 is taken care of by summing the n=0 and n=1 cases. The point of the Fibonacci sequence is that you only need to define the first *two* elements. Defining the first two as 0 and 1 is equivalent to defining them as 1 and 1 (it just shifts the sequence over by one). In fact, you can define a Fibonacci-type sequence with any two starting values. The sequences are different, but the ratio fib(n)/fib(n-1) is asymptotically the same for all of them. Try generalizing your program to take the starting elements of the sequence as parameters (they could be part of the constructor).

Hint for the more efficient method: Often, making something more efficient means using just a wee bit more storage (for intermediate results).

Cheers, Rick [ March 15, 2005: Message edited by: Rick Goldstein ]