Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!

kelvin cheung
Ranch Hand
Posts: 120
hi.

i have to write a recursive code that calculates Fibonacci numbers.
http://math.holycross.edu/~davids/fibonacci/fib0-99.html

with a given argument "n", for example 11,
the console should display "fib(11)=89".

i tried to write the code, which didn't do what i wanted :

output is:

method argument: 4
method argument: 2
return 1
method argument: 1

any ideas would be appreciated ^^"

regards,
kelvin

Carol Enderlin
drifter
Ranch Hand
Posts: 1364
Looks like you need one more print statement to diagnose the problem within the fibonacci() method.

fred rosenberger
lowercase baba
Bartender
Posts: 12087
29
don't you need two base cases for the fibbinaci's? what happens in your code when you pass in the method argument of 1?

kelvin cheung
Ranch Hand
Posts: 120
hm.. it never goes back to the println in the constructor

Horatio Westock
Ranch Hand
Posts: 221
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 ]

Henry Wong
author
Marshal
Posts: 20902
76
The key is the last phrase ... "method argument: 1".

It will be follow by a fib(n-2), which is fib(-1), which will execute the System.exit() method.

Henry

kelvin cheung
Ranch Hand
Posts: 120
hello,
thanks for the replies!

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
Posts: 221
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
Posts: 120
hello,

it was useful.

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

regards,
kelvin.

Rick Goldstein
Greenhorn
Posts: 21