aspose file tools*
The moose likes Java in General and the fly likes please help me with Recursion Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "please help me with Recursion" Watch "please help me with Recursion" New topic
Author

please help me with Recursion

kelvin cheung
Ranch Hand

Joined: Mar 27, 2004
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

Joined: Oct 10, 2000
Posts: 1364
Looks like you need one more print statement to diagnose the problem within the fibonacci() method.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11314
    
  16

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?


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
kelvin cheung
Ranch Hand

Joined: Mar 27, 2004
Posts: 120
hm.. it never goes back to the println in the constructor
Horatio Westock
Ranch Hand

Joined: Feb 23, 2005
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
Sheriff

Joined: Sep 28, 2004
Posts: 18845
    
  40

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


Books: Java Threads, 3rd Edition, Jini in a Nutshell, and Java Gems (contributor)
kelvin cheung
Ranch Hand

Joined: Mar 27, 2004
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

Joined: Feb 23, 2005
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

Joined: Mar 27, 2004
Posts: 120
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 ^^

regards,
kelvin.
Rick Goldstein
Greenhorn

Joined: Oct 10, 2003
Posts: 21
Just two pedantic comments:

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 ]
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: please help me with Recursion