CODEWITHSUNDEEP
javarecursion
J.Doe
J.Doe

Reputation: 9

Finding Geometric sum using recursion

I am trying to better understand recursion. I am writing a basic geometric series method which I know could be done easier with a loop but that is not the purpose. The method is producing the currect output for the values of 0 and 1 which is simply 1 and 1.5. But for 2 it is outputting 1.25 when it should be 1.75. Any pointers on a better way to approach this?

public static double geometricSum(int n) {
    if(n == 0){
        return 1;
    }
    n = n * 2;
    return 1.0 / n + geometricSum((int) (1/Math.pow(2, n)));
}

Upvotes: 0

Views: 5312

Answers (4)

vijayraj34
vijayraj34

Reputation: 2415

This is my python code:

 def geometricSum(k):
     if k == 0:
         return 1
     return 1/2**k + geometricSum(k-1)


 k = int(input()) 
 print(geometricSum(k))

This is all about the power of 2 i.e. 2 Pow n where n is an integer.

Here Recursion is used to get the sequence of values for n. In my case I've to calculate the value for 1/(2 pow n).

Upvotes: 0

jrtapsell
jrtapsell

Reputation: 7001

The first problem is the cast to int, giving the wrong result, already described by reyeselda95.

There is a second problem hidden, which is that if you fix that you get this:

public static double geometricSum(double n) {
    System.err.println("Calling with " + n);
    if(n == 0){
      return 1;
    }
    n = n * 2;
    return 1.0 / n + geometricSum((1/Math.pow(2, n)));
  }

Calling this with the provided value of 2, leads to a loop between calls with the following values, leading to a stack overflow.

...
Calling with 0.4999999999999999
Calling with 0.5000000000000001
Calling with 0.4999999999999999
Calling with 0.5000000000000001
...

This may be the function you are looking for, if I understand correctly:

public static double geometricSum(int count) {
    if (count == 0) {
      return 1;
    }
    return geometricSum(count-1) + Math.pow(2, -count);
}

Upvotes: 0

andrey4623
andrey4623

Reputation: 81

  1. Don't cast float to int;
  2. When using float, are you sure your formula is correct? The recursion breaks if an argument is zero, but you will get StackOverflowError when passing the result of 1.0/Math.pow(2, n) to the function.

Upvotes: 0

Reyeselda95
Reyeselda95

Reputation: 36

This happens because you are casting a float into a int. 

1/(2^2)=1/4=0.25 --> 0

As you are passing your float as an int you're not getting your thing working propperly. So 0.25 + geometricSum(0)=1.25. On the first one happens the same. you pass the 0.5, but turned into an int so you.re not getting your aproximation propperly done.

As an advice, ALWAYS put () on your math functions in order to make the program, and you yourself, understand in which order it computes the numbers.

Upvotes: 1

Related Questions