John Smith
John Smith

Reputation: 167

Arithmetic Recursion

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

Upvotes: 6

Views: 123

Answers (3)

Bathsheba
Bathsheba

Reputation: 234885

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

  1. You need to compute each term using floating point division. Rewrite as 1.0 / n.

  2. Drop the term 1.0 / 0 as that will give you an infinite floating point value.

  3. 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.

Upvotes: 0

mazhar islam
mazhar islam

Reputation: 5629

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;

Upvotes: 2

Eran
Eran

Reputation: 394156

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.

Upvotes: 10

Related Questions