CODEWITHSUNDEEP
javarecursionpascals-triangle
user2932450
user2932450

Reputation: 71

Recursive method for Pascal's triangle

I have written a method to evaluate a Pascal's triangle of n rows. However when I test the method I receive the error:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1

Here is the code:

public static int[] PascalTriangle(int n) {
    int[] pt = new int[n + 1];
    if (n == 0) {
        pt[0] = 1;
        return pt;
    }
    int[] ppt = PascalTriangle(n - 1);
    pt[0] = pt[n] = 1;
    for (int i = 0; i < ppt.length; i++) {
        pt[i] = ppt[i - 1] + ppt[i];
    }
    return pt;
}

Please let me know if you have any ideas for how the code could be edited to fix the problem.

Upvotes: 0

Views: 23957

Answers (5)

Clemson
Clemson

Reputation: 506

Here is some code a friend of mine came up with

import java.util.Scanner;
public class Pascal {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    System.out.print("Enter the number of rows to print: ");
    int rows = scanner.nextInt();
    System.out.println("Pascal Triangle:");
    print(rows);
    scanner.close();
  }

  public static void print(int n) {
    for (int i = 0; i < n; i++) {
      for (int k = 0; k < n - i; k++) {
        System.out.print(" "); // print space for triangle like structure
      }
      for (int j = 0; j <= i; j++) {
        System.out.print(pascal(i, j) + " ");
      }
      System.out.println();
    }
  }

  public static int pascal(int i, int j) {
    if (j == 0 || j == i) {
      return 1;
    } else {
      return pascal(i - 1, j - 1) + pascal(i - 1, j);
    }
  }
}

Upvotes: 3

austinw
austinw

Reputation: 734

This isn't the solution to your code but it is solution to printing Pascals Triangle using only recursion which means no loops, using the combinations formula. All it needs is a main method or demo class to create an instance of the PascalsTriangle class. Hope this helps future Java students.

public class PascalsTriangle {

private StringBuilder str; // StringBuilder to display triangle

/**
 * Starts the process of printing the Pascals Triangle
 * @param rows Number of rows to print
 */
public PascalsTriangle(int rows) {

    str = new StringBuilder();

    printTriangle(rows, str);
}

/**
 * Uses recursion to function as an "outer loop" and calls
 * itself once for each row in triangle. Then displays the result
 * @param row The number of the row to generate
 * @param str StringBuilder to insert each row into
 */
public static void printTriangle(int row, StringBuilder str) {

    // calls itself until row equals -1
    if (row >= 0) {

        // calls lower function to generate row and inserts the result into front of StringBuilder
        str.insert(0, getRow(row, 0) + "\n");

        // calls itself with a decremented row number
        printTriangle(row - 1, str);
    } else {

        // when the base case is reached - display the result
        JOptionPane.showMessageDialog(null, str);
        System.exit(0);
    }
}

/**
 * Uses recursion to act as the "inner loop" and calculate each number in the given row
 * @param rowNumber Number of the row being generated
 * @param elementNumber Number of the element within the row (always starts with 0)
 * @return String containing full row of numbers or empty string when base case is reached
 */
public static String getRow(int rowNumber, int elementNumber) {

    // calls itself until elementNumber is greater than rowNumber
    if (elementNumber <= rowNumber) {

        // calculates element using combinations formula: n!/r!(n-r)!
        int element = fact(rowNumber) / (fact(elementNumber) * (fact(rowNumber - elementNumber)));

        // calls itself for each element in row and returns full String            
        return element + " " + getRow(rowNumber, elementNumber + 1);

    } else return "";
}

/**
 * Helper function that uses recursion to calculate factorial of given integer
 * @param n Number to calculate factorial
 * @return Factorial
 */
public static int fact(int n) {
    if (n <= 0)
        return 1;
    else
        return n * fact(n - 1);
}

Upvotes: 0

NeeK
NeeK

Reputation: 902

Improvement in @Clemson code using Dynamic Programming : 

class Solution {
    int[][] dp ; 
    public List<List<Integer>> generate(int numRows) {
        dp = new int[numRows][numRows];

        List<List<Integer>> results = new ArrayList<>();
        pascal(results, numRows);

        return results;
    }

    private void pascal(List<List<Integer>> results, int numRows) {
        for(int i = 0; i < numRows; i++) {
            List<Integer> list = new ArrayList<>();
            for(int j = 0; j <= i ; j++) {
                list.add(dfs(i, j));
            }
            results.add(list);
        }
    }

    private int dfs(int i, int j) {
        if(j == 0 || i == j) return 1;

        if(dp[i][j] != 0) return dp[i][j];

        return dp[i][j] = dfs(i - 1, j - 1) + dfs(i - 1, j );
    }

}

Upvotes: 0

Karthik T
Karthik T

Reputation: 31952

for(int i = 0; i < ppt.length; i++)
    {
        pt[i] = ppt[i-1] + ppt[i];

In your first iteration, i == 0 and so (i-1) == -1. This is the cause of the error.

You can special handle the boundaries to avoid this. Or as the others have suggested, start i at 1 instead of 0.

Upvotes: 4

ajb
ajb

Reputation: 31689

In this code:

pt[0] = pt[n] = 1;
for(int i = 0; i < ppt.length; i++)
{
    pt[i] = ppt[i-1] + ppt[i];
}

the problem is that when i is 0, you're trying to access ppt[i-1] which is ppt[-1]. The thing to notice is that when i is 0, you don't need to execute the statement that sets pt[i], because you already set pt[0] up before the loop! Try initializing i to 1 instead of 0.

Upvotes: 0

Related Questions