Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

please help me with Recursion

 
kelvin cheung
Ranch Hand
Posts: 120
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Looks like you need one more print statement to diagnose the problem within the fibonacci() method.
 
fred rosenberger
lowercase baba
Bartender
Posts: 12087
29
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
hm.. it never goes back to the println in the constructor
 
Horatio Westock
Ranch Hand
Posts: 221
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 20902
76
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 21
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic