# please help me with Recursion

kelvin cheung

Ranch Hand

Posts: 120

posted 11 years ago

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:

any ideas would be appreciated ^^"

regards,

kelvin

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

Ranch Hand

Posts: 1364

kelvin cheung

Ranch Hand

Posts: 120

Horatio Westock

Ranch Hand

Posts: 221

posted 11 years ago

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 ]

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 ]

kelvin cheung

Ranch Hand

Posts: 120

posted 11 years ago

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?

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

posted 11 years ago

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 ]

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

Rick Goldstein

Greenhorn

Posts: 21

posted 11 years ago

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 ]

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 ]