CODEWITHSUNDEEP
javaarraysrecursion
pepsimonster
pepsimonster

Reputation: 11

Pascal Triangle Java exercise with recursion to return coefficients of (1+x)^n in an array

This method will return the coefficients of the expansion of (1 + x)^n in an array (i.e., put the (n+1)^th row of Pascal’s Triangle in an array. For example, suppose c = PascalTriangle(n). Then, c[i] is the coefficient of x^i in the expansion of (1 + x)^n.

My code so far is the following:

static int[] pascalTriangle(int n)
{
    int [] a = new int [n+1];
    if(n == 0) {
        a[0] = 1;
        return a;
    }

    int[] s = pascalTriangle(n-1);
    a[0] = a[n-1] = 1;

    for(int i = 0; i < n-1; i++) {
        a[i] = s[i-1] + s[i];
    }
    return a;
}

Test code: 

    public static void testPascalTriangle() 
    {
        for (int n = 0; n <= 30; n+=5) {

            String str="(1+x)^"+n+":";
            int[] c = Recursion.pascalTriangle(n);

            for (int i = 0; i < c.length; i++) 
                str += " " + c[i]; 
            System.out.println(str);
    }
}

My problem I believe is getting past the first if statement in my code since it outputs: (1+x)^0: 1. Then I get an index out of bounds error, I think it doesn't reach the a[0] line and beyond which I need it to do.

Thanks for any help.

Upvotes: 1

Views: 257

Answers (1)

Jean-Fran&#231;ois Savard
Jean-Fran&#231;ois Savard

Reputation: 21004

The AIOOBE happens in this snippet

for (int i = 0; i < n - 1; i++) {
    a[i] = s[i - 1] + s[i];
}

When i is equal to 0, it will try to retrieve s[-1] which is not a legal bound.

I believe, since you are looping until i < n - 1 that you should use instead

a[i] = s[i] + s[i + 1];

Then you would get the output

(1+x)^0: 1
(1+x)^5: 5 3 2 1 1 0
(1+x)^10: 55 34 21 13 8 5 3 2 1 1 0
(1+x)^15: 610 377 233 144 89 55 34 21 13 8 5 3 2 1 1 0
(1+x)^20: 6765 4181 2584 1597 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1 1 0
(1+x)^25: 75025 46368 28657 17711 10946 6765 4181 2584 1597 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1 1 0
(1+x)^30: 832040 514229 317811 196418 121393 75025 46368 28657 17711 10946 6765 4181 2584 1597 987 610 377 233 144 89 55 34 21 13 8 5 3 2 1 1

Upvotes: 3

Related Questions