Search code examples
javarecursionmathpi

Recursive implementation of the Wallis function in Java


This is the Wallis function:

enter image description here

I'm struggling to implement it recursively. This is my best attempt:

private static double computePiOver2(int n) {
    int original_n = n;
    double prod = 1.0;
    int reps = 0;

    if(reps == original_n)
        return prod;
    else {
        reps += 1;
        n += 1;
        prod *= computePiOver2(2*n/(2*n-1)*(2*n/(2*n+1)));
        return prod;
    }

I'm testing it using this code

public static void main(String[] args) {
    for(int i = 0; i < 100; i++){
       System.out.println(Math.PI/2 + " vs. " + computePiOver2(i));
    }
}

But my answer is always 1.0. What am I doing incorrectly?

I tried making n a double:

private static double computePiOver2(double n) {
        int original_n = (int) n;
        double prod = 1.0;
        int reps = 0;

        if(reps == original_n)
            return prod;
        else {
            reps += 1;
            n += 1;
            prod *= computePiOver2(2*n/(2*n-1)*(2*n/(2*n+1)));
            return prod;
        }
    }

But I just get a stackoverflow error.


Solution

  • I had two errors, integer division (thanks @azurefrog) and incorrect recursion technique (thanks @David M). I was supposed to compute the recursive call like this

    (2n/(2n-1))*(2n/(2n+1)) * computePiOver2(n-1)
    

    Here is the working function:

    private static double computePiOver2(int n) {
        double prod = 1.0;
        int reps = 0;
    
        if(reps == n)
            return prod;
        else {
            reps += 1;
            return 2.0*n/(2*n-1)*(2.0*n/(2*n+1)) * computePiOver2(n-1);
        }
    }