11

I'm really getting the hang of recursion (or so I think), but this problem is tripping me up. I'm trying to return 1 + 1/2 + 1/3 + ... + 1/n, but no matter what I try the method returns 1.0. I cannot for the life of me figure out what's wrong.

public static double harmonic(int n) {
    if(n == 1) {
        return 1;
    } else {
        return (1 / n) + (1 / harmonic(n - 1));
    }
}
vaindil
  • 7,536
  • 21
  • 68
  • 127
  • Have you checked this with a debugger step by step? – Zavior Oct 15 '12 at 21:28
  • 5
    Use doubles in your division calculations, i.e. `(1.0 / n)`. – FThompson Oct 15 '12 at 21:29
  • Yes, I did. It's difficult for me to follow recursion problems through a debugger, however, as there are so many levels that it's tough to follow what's going on. – vaindil Oct 15 '12 at 21:29
  • You may also want to protect against the infinite recursion you'll get if a zero or negative number is mistakenly passed for `n`. – RBarryYoung Oct 15 '12 at 21:35
  • Yeah, I would normally make the base case `if(n <= 1) {`, but this is for an online submission system and for some reason it's only accepting what I currently have. – vaindil Oct 15 '12 at 21:37

9 Answers9

13

You want to use floating point division:

public static double harmonic(int n) {
    if(n == 1.0) {
        return 1.0;
    } else {
        return (1.0 / n) + (1.0 / harmonic(n - 1.0));
    }
}

That is: 1/2 is 0; 1/2.0 is 0.5.

Claudiu
  • 224,032
  • 165
  • 485
  • 680
  • Ah, that's part of the problem, but I also implemented my formula incorrectly (it should be `return (1.0 / n) + harmonic(n - 1);`. Thank you! – vaindil Oct 15 '12 at 21:33
  • 1
    glad i could help! I only sought to point out why you were getting '0', not anything beyond that point. Brian went the extra mile – Claudiu Oct 16 '12 at 04:05
10

Well, for one, you don't want to return (1 / n) + (1 / harmonic(n - 1)), but also you need to use double arithmetic:

public static double harmonic(int n) {
    if(n == 1) {
        return 1.0;
    } else {
        return (1.0 / n) + harmonic(n - 1);
    }
}

If you left it as 1 / harmonic you'd return another function entirely:

(1 / n) + 1 / ( 1 / (n - 1) + 1 / ( 1 / (n - 2) + 1 / (...) ) )

That is a very confusing function to figure out, btw, but I think (with my 3rd time editing it) I got it right this time.

Brian
  • 17,079
  • 6
  • 43
  • 66
  • That's it! Others suggested using doubles, which was definitely part of the problem, but you also got the correction in the `return` statement. Thank you! – vaindil Oct 15 '12 at 21:34
2

Thats because integer division gives integer result.

So, 1/2 == 0

You can use rather use floating-point division like this: -

if(n == 1.0) {
    return 1.0;
} else {
    return (1.0 / n) + harmonic(n - 1); // Should be `harmonic(n - 1)`
}
Rohit Jain
  • 209,639
  • 45
  • 409
  • 525
2

You need to use doubles. Right now, you're doing 1 / n, both of which are integers. Change it to:

return (1.0 / n) + (1.0 / harmonic(n - 1));
paddy
  • 60,864
  • 6
  • 61
  • 103
1

Use doubles in your division calculations. Currently, everything is cast to ints, losing any floating-point precision you would normally expect.

public static double harmonic(int n) {
    if (n == 1) {
        return 1;
    } else {
        return (1.0 / n) + (1.0 / harmonic(n - 1));
    }
}
FThompson
  • 28,352
  • 13
  • 60
  • 93
1

the recursion part should not include 1/harmonic(n-1) it should be 

   public static double harmonic(int n)
  {
    double harm = 0.0;
    if (n == 1) {
        return 1.0;
    }
    else {
        harm = harm + (1.0 / n) +  harmonic(n - 1);
    }
    return harm;

}
Seid.M
  • 185
  • 7
0
/**
 * Created by hrishikesh.mishra on 04/01/16.
 *
 * Describe a recursive algorithm
 * for computing the nth Harmonic number,
 * defined as Hn = ∑ n k=1 1/k.
 *
 */
public class HarmonicNumber {


    public static void main(String[] args) {

        System.out.println("Sum up to 1: "  + sum(1));
        System.out.println("Sum up to 2: "  + sum(2));
        System.out.println("Sum up to 3: "  + sum(3));
        System.out.println("Sum up to 4: "  + sum(4));
    }


    /**
     * Summation with recursive method.
     * @param n
     * @return
     */
    public static double sum(int n){
        if(n <= 1)
            return 1;
        else
            return ((double) 1/n) + sum(n - 1);
    }
}
Hrishikesh Mishra
  • 3,295
  • 3
  • 27
  • 33
0

This is my implementation of the harmonic number recursion.

double harmonic(int n){

    if(n == 1)return 1;
    else return 1.0 / n + harmonic(n - 1);

}
voxelfox
  • 23
  • 2
-1
 public static double harmonic(int n)
   {
      if (n==1)
      return 1/n;
      else return 1/n + harmonic(n-1);
   }
Mahmoud
  • 1