programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Recursion Reciprocals

Teri Fisher
Ranch Hand
Posts: 52
I need to write a recursion method with one argument returning a double value which is the sum of the reciprocals of the first n positive integers. eg sumover(1), sumover(2) and sumover(3) would be 1/1 + 1/2 + 1/3 returning approx 1.833 but I'm not sure how to add the fractions in recursion

marc weber
Sheriff
Posts: 11343
See this topic on recursion, and let us know if it helps.

Teri Fisher
Ranch Hand
Posts: 52
I looked at that earlier but I can't use any local variables.

marc weber
Sheriff
Posts: 11343
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?

Campbell Ritchie
Marshal
Posts: 56576
172
Are you supposed to get 1.833... as a result? I seem to think I have seen the same recursion or something similar which is supposed to return 1.618...

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

A recursive call has the following characteristics:
• 1: A method calls itself. Whatever the method is called, somewhere in it there is a call to THE SAME method.
• 2: Each call is slightly simpler than the previous call: often you call someMethod(n - 1)
• 3: There has to be a base call, often where n is 0 or n is 1.
• No 1 is absolutely essential to a recursion. Nos 2 and 3 are optional, but if you miss them out you will end up with an infinite call stack. Actually it won't be infinite; you will exhaust the memory available and crash the system before that!

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 ints 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 ]

Garrett Rowe
Ranch Hand
Posts: 1296
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 ]

Teri Fisher
Ranch Hand
Posts: 52
Yes, the method is supposed to return a double value and 1/1 + 1/2 + 1/3 would be 1.833....
Thanks for the suggestions, I'll see what I can come up with.

Campbell Ritchie
Marshal
Posts: 56576
172
Originally posted by Garrett Rowe:
Campbell Ritchie: No 1 is absolutely essential to a recursion.

Not necessarily.
Touche.

Guido Sautter
Ranch Hand
Posts: 142
Hi Teri,

you might try this one:

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

f. nikita thomas
Ranch Hand
Posts: 87
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 ]

marc weber
Sheriff
Posts: 11343
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.

Teri Fisher
Ranch Hand
Posts: 52
I know I'm supposed to call my method within my method, right? Even with this code I can't figure out how I'm getting this output.

sumover(2):
0.5
1.5
2.5
3.5
4.5

marc weber
Sheriff
Posts: 11343
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.

Garrett Rowe
Ranch Hand
Posts: 1296
Any "for loop" can be replaced with an equivalent recursive call:

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 ]

marc weber
Sheriff
Posts: 11343
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.

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.

f. nikita thomas
Ranch Hand
Posts: 87
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 ]

Campbell Ritchie
Marshal
Posts: 56576
172
Originally posted by Teri Fisher:
. . .
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.

Teri Fisher
Ranch Hand
Posts: 52
Thanks to everyone who helped me with this! I appreciate your time and patience.

Garrett Rowe
Ranch Hand
Posts: 1296
Good job. I'm glad you were able to get it figured out.

marc weber
Sheriff
Posts: 11343
Excellent!

Campbell Ritchie
Marshal
Posts: 56576
172
Well done

Campbell Ritchie
Marshal
Posts: 56576
172
I think you would do better, however, to change the parameter type from double to int. Otherwise there is the risk of your getting a value of 0.999999999999999... or 1.0000000000001... or similar and missing the n == 1 test and getting an exception.
Tiny enhancement: change the return value from 1 to 1.0.

Teri Fisher
Ranch Hand
Posts: 52
Minor enhancement done...Thanks!