wood burning stoves 2.0*
The moose likes Beginning Java and the fly likes Recursion Reciprocals Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Recursion Reciprocals" Watch "Recursion Reciprocals" New topic
Author

Recursion Reciprocals

Teri Fisher
Ranch Hand

Joined: Jan 07, 2008
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

Joined: Aug 31, 2004
Posts: 11343

See this topic on recursion, and let us know if it helps.


"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
Teri Fisher
Ranch Hand

Joined: Jan 07, 2008
Posts: 52
I looked at that earlier but I can't use any local variables.
marc weber
Sheriff

Joined: Aug 31, 2004
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
Sheriff

Joined: Oct 13, 2005
Posts: 37980
    
  22
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

    Joined: Jan 17, 2006
    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 ]

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

    Joined: Jan 07, 2008
    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
    Sheriff

    Joined: Oct 13, 2005
    Posts: 37980
        
      22
    Originally posted by Garrett Rowe:
    Campbell Ritchie: No 1 is absolutely essential to a recursion.

    Not necessarily.
    Touche.
    Guido Sautter
    Ranch Hand

    Joined: Dec 22, 2004
    Posts: 142
    Hi Teri,

    you might try this one:


    [ April 14, 2008: Message edited by: marc weber ]
    f. nikita thomas
    Ranch Hand

    Joined: Mar 02, 2008
    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 ]

    Imagination is more important than knowledge "Albert Einstein"
    marc weber
    Sheriff

    Joined: Aug 31, 2004
    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

    Joined: Jan 07, 2008
    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

    Joined: Aug 31, 2004
    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

    Joined: Jan 17, 2006
    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

    Joined: Aug 31, 2004
    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

    Joined: Mar 02, 2008
    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
    Sheriff

    Joined: Oct 13, 2005
    Posts: 37980
        
      22
    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.

    Please read the hints everybody else is giving.
    Teri Fisher
    Ranch Hand

    Joined: Jan 07, 2008
    Posts: 52
    Thanks to everyone who helped me with this! I appreciate your time and patience.
    Garrett Rowe
    Ranch Hand

    Joined: Jan 17, 2006
    Posts: 1296
    Good job. I'm glad you were able to get it figured out.
    marc weber
    Sheriff

    Joined: Aug 31, 2004
    Posts: 11343

    Excellent!
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 37980
        
      22
    Well done
    Campbell Ritchie
    Sheriff

    Joined: Oct 13, 2005
    Posts: 37980
        
      22
    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

    Joined: Jan 07, 2008
    Posts: 52
    Minor enhancement done...Thanks!
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Recursion Reciprocals
     
    Similar Threads
    Iterative Fibonacci Method Problem
    Recursion
    Java Recursion and binary tree searching questions
    The math nature of a primitive recursive function
    Timing Methods