CODEWITHSUNDEEP
javarecursion
vaindil
vaindil

Reputation: 7854

Not sure how to handle this simple recursion with fractions

I have to write a simple recursion method to calculate m(i) = (1/2) + (2/3) + ... + i/(i+1). I feel like this should be incredibly simple, but I cannot figure it out. I know that I have to loop by decrementing, but I just can't get it. So far I have the following, which I know is completely wrong.

public class Recursion {
    public static void main(String[] args) {

        double n = run(10);
        System.out.print("Result: " + n);
    }

    public static double run(double nb) {
        double result = 0;

        if(nb == 2){
            return 1/2;
        }

        result += run(nb - 2) / run(nb - 1);
        return result;

    }

}

Upvotes: 0

Views: 817

Answers (4)

Ted Hopp
Ted Hopp

Reputation: 234795

Use this recurrence relation:

m(i) = i/(i+1) + m(i-1)

In code, it might look like this:

public static double run(int i) {
    if (i < 1) {
        return 0;
    }
    return i / (i + 1.0) + run(i - 1);
}

Note that there's no need for the argument to be floating point, just the return value.

Upvotes: 2

Tom G
Tom G

Reputation: 3650

Try this:

public class Recursion{
    public static void main(String[] args) {
        double n = run(10);
        System.out.print("Result: " + n);
    }

    public static double run(double nb) {
        double result = 0;
        if(nb > 1){
            result = nb/(nb + 1) + run(nb - 1);
        } else{
            result = nb/(nb + 1);
        }
        return result;
    }
}

Upvotes: 2

Samuel EUSTACHI
Samuel EUSTACHI

Reputation: 3156

I think you should replace this 

result += run(nb - 2) / run(nb - 1);

By

result += nb - 2 / nb - 1;
return result + run(nb - 1);

Upvotes: 0

Aditya Jain
Aditya Jain

Reputation: 1095

trying a bit math should make this simple.

m(i) = 1/2 + 2/3 +....+(i)/(i+1)
or m(i) = 2/2-1/2 + 3/3-1/3 + ....+ (i+1)/(i+1) - 1/(i+1)
or m(i) = 1-1/2 + 1 - 1/3 +...(i times)..+ 1 - (1/(i+1))
or m(i) = i - ( 1/2 + 1/3 + ... + 1/(i+1) )

Now it should be easy to write a algorithm for this.

Upvotes: 0

Related Questions