• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Recursion Reciprocals

 
Ranch Hand
Posts: 52
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Sheriff
Posts: 11343
Mac Safari Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
See this topic on recursion, and let us know if it helps.
 
Teri Fisher
Ranch Hand
Posts: 52
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I looked at that earlier but I can't use any local variables.
 
marc weber
Sheriff
Posts: 11343
Mac Safari Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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?
 
Marshal
Posts: 79177
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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 ]
     
    Ranch Hand
    Posts: 1296
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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: 79177
    377
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

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

    Not necessarily.

    Touche.
     
    Ranch Hand
    Posts: 142
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Hi Teri,

    you might try this one:


    [ April 14, 2008: Message edited by: marc weber ]
     
    Ranch Hand
    Posts: 87
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    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
    Mac Safari Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    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
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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
    Mac Safari Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    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
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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
    Mac Safari Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    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: 79177
    377
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    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
    Posts: 52
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Thanks to everyone who helped me with this! I appreciate your time and patience.
     
    Garrett Rowe
    Ranch Hand
    Posts: 1296
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Good job. I'm glad you were able to get it figured out.
     
    marc weber
    Sheriff
    Posts: 11343
    Mac Safari Java
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Excellent!
     
    Campbell Ritchie
    Marshal
    Posts: 79177
    377
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Well done
     
    Campbell Ritchie
    Marshal
    Posts: 79177
    377
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    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
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Minor enhancement done...Thanks!
     
    reply
      Bookmark Topic Watch Topic
    • New Topic