Arithmetic Recursion

Question

I am trying to write a code that computes the following for a given integer n:

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

This is the code I have written so far:

public class RecursiveSum
{
  public static double Sumto(int n)
  {
    if (n == 0) { return 0.0; }
    else if (n > 0) { return 1/n + 1/Sumto(n - 1); }
    else { throw new IllegalArgumentException("Please provide positive integers"); }
  }
  public static void main(String[] args)
  {
    System.out.println(Sumto(5));
  }
}

However, it always outputs:

Infinity

What is the problem and how can I fix it?

Thank you

Instead of recursion a for-loop over 1 to n might be simpler and less error-prone here. — johannesv, Aug 03 '15 at 09:28

score 10 · Accepted Answer · answered Aug 03 '15 at 09:23

You have two issues :

You must perform floating point division (i.e. replace 1/n with 1.0/n), and you should add Sumto(n - 1) to 1.0/n to get Sumto(n).

  public static double Sumto(int n)
  {
    if (n == 0) { return 0.0; }
    else if (n > 0) { return 1.0/n + Sumto(n - 1); }
    else { throw new IllegalArgumentException("Please provide positive integers"); }
  }

The reason you got Infinity was that 1/Sumto(n - 1) returns Infinity when Sumto(n - 1) is 0.0, and Sumto(0) is 0.0.

score 2 · Answer 2 · edited May 23 '17 at 12:06

However, it always outputs: Infinity

Because you are doing 1/0 in the following steps in your code which yields Infinity.

else if (n > 0) { return 1/n + 1/Sumto(n - 1);

You thought n > 0 escapes the n / 0 stuffs, but nope! Think about the case when n = 1 which passes n > 0 case but fall into a trap to:

1/Sumto(n - 1)
1/Sumto(1 - 1)
1/Sumto(0)

where Sumto(0) returns 0.0. Hence,

 1/0.0

yields Infinity. Moreover, use 1.0/n instead of 1/n as it is floating point division.

So add another condition, like

if(n == 1) 
    return 1;

Bathsheba · Answer 3 · 2015-08-03T10:02:56.527

A few problems, nothing first that since there is no closed form expression for the harmonic series.

You need to compute each term using floating point division. Rewrite as 1.0 / n.
Drop the term 1.0 / 0 as that will give you an infinite floating point value.
You'll get better accuracy if you reverse the loop. That is, compute the smaller terms first. Otherwise you'll underestimate the sum with floating point arithmetic. As a rule of thumb, always add small numbers first.

Arithmetic Recursion

3 Answers3