# Recursion Reciprocals

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." *~Joe Strummer*

sscce.org

Originally posted by Teri Fisher:

I looked at that earlier but I can't use any local variables.

Well, I would say that whenever you pass an argument to a method, you have a local variable. But you can still write a recursive method that acts on variables in a wider scope.

The idea behind recursion is that a method calls itself. In this case, that happens n times (or maybe n-1, depending on how you structure it). So ask yourself: What do you want to "do" n times?

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." *~Joe Strummer*

sscce.org

1.618... is the golden ratio which is (1 + sqrt5)/2.

A recursive call has the following characteristics:

So . . .

You ought to have a call INSIDE THE sumover method to sumover(n - 1).

You will need to return something like 1 + sumover(n - 1).

You cannot use 1 / n because both numbers are

*int*s and 1 / n will return 0 if n is greater than 1. You will have to cast one (or both) of the numbers to a double. Maybe using

*1d / n*is the simplest way to do it. (Or

*1.0 / n*.)

Change your if to throw the exception if

*n <= 0*. (Or

*n < 1*.)

I think at this point, I have told you as much as I can short of giving you a straight solution. Good luck putting it together.

[ April 13, 2008: Message edited by: Campbell Ritchie ]

**Campbell Ritchie: No 1 is absolutely essential to a recursion.**

Not necessarily, consider this contrived example, neither method directly calls itself, but its definitely recursive:

[ April 14, 2008: Message edited by: Garrett Rowe ]

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

Originally posted by Guido Sautter:

Hi Teri,

you might try this one:

is this really the type of help they need? just giving the answer really doesn't help them understand the concept. i have one of the most difficult instructors for undergraduate level java, however if i have a concern i'd rather be humble and ask for "hints" than have someone hand it to me. just my dos centavo's

[ April 14, 2008: Message edited by: marc weber ]

Imagination is more important than knowledge "Albert Einstein"

Originally posted by f. nikita thomas:

...is this really the type of help they need? just giving the answer really doesn't help them understand the concept...

Right. Or as it says at the top of the Beginners forum...

We're all here to learn, so when responding to others, please focus on helping them discover their own solutions, instead of simply providing answers.

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." *~Joe Strummer*

sscce.org

Originally posted by Teri Fisher:

...I can't figure out how I'm getting this output...

Your output is all coming from this loop, where n is 2.0...

So you're starting with 1/2, then incrementing that by 1 until it's 5 or more.

*~Joe Strummer*

sscce.org

In a loop the variable that changes is the loop index, in recursion the variable that changes is the method parameter, they both cede control when that variable exceeds some threshold (i.e. when (i >= times) looping, or when (times == 0) recursively). So remembering that, if you had to generate the series:

1/1 + 1/2 + 1/3 + 1/4.. 1/n

using a loop how do you think you would do that?

Do you see a way to translate that loop directly into a recursive method?

How could you translate that loop into recursive code?

[ April 14, 2008: Message edited by: Garrett Rowe ]

[ April 14, 2008: Message edited by: Garrett Rowe ]

Some problems are so complex that you have to be highly intelligent and well informed just to be undecided about them. - Laurence J. Peter

When n = 2, you want 1/1 + 1/2.

When n = 3, you want 1/1 + 1/2 + 1/3.

When n = 4, you want 1/1 + 1/2 + 1/3 + 1/4.

And so on.

Now, as you look at this pattern, ask yourself how it's building

**on itself**. Notice that...

When n = 4, you have

*something*plus the result of when n = 3. So what do you have when n = 3?

When n = 3, you have

*something*plus the result of when n = 2. So what do you have when n = 2?

When n = 2, you have

*something*plus the result of when n = 1. So what do you have when n = 1?

When n = 1, you have 1/1.

This is the basis for your recursion. Try to carefully describe these steps in English before trying to code it in Java.

*~Joe Strummer*

sscce.org

Originally posted by marc weber:

When n = 1, you want 1/1.

When n = 2, you want 1/1 + 1/2.

When n = 3, you want 1/1 + 1/2 + 1/3.

When n = 4, you want 1/1 + 1/2 + 1/3 + 1/4.

And so on.

so if you rearrange the terms a pattern shows up:

1 + 1/4 + 1/3 + 1/2

if you look closely the terms are decreasing!

**(big freakin' hint!)**now how do you express the decreasing terms in respect to (n) which in this case is 4. your base case is 1 since it is the last term you will return. the general case is what is left!

[ April 15, 2008: Message edited by: f. nikita thomas - darn tags!]

[ April 15, 2008: Message edited by: f. nikita thomas ]

Imagination is more important than knowledge "Albert Einstein"

1 / n - 1 doesn't do what you think it does; / has a higher precedence than - so what you meant to write was 1 / (n - 1). But even that isn't as you think recursive, and it isn't giving you the right answer.Originally posted by Teri Fisher:

. . .

Please read the hints everybody else is giving.

*~Joe Strummer*

sscce.org

Tiny enhancement: change the return value from 1 to 1.0.