java - 递归方法导致 java.lang.StackOverflowError

Question

我正在尝试创建帕斯卡的三角形，以及这条线：

return pascalTriangle(row-1, col-1) + pascalTriangle(row-1, col);

int在返回帕斯卡三角形中的值的递归方法中，导致

Exception in thread "main" java.lang.StackOverflowError

它只打印一行1，然后为其他行抛出异常。我需要修复什么以使其不会引发任何异常并形成帕斯卡三角形？这是我的代码：

import java.util.Scanner;

/**
 * This program takes n input from the user, and forms
 * Pascal's Triangle in n number of rows that the user entered.
 */
public class DD_PascalsTriangle {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("Enter an integer: ");
        // the number of rows created in the Pascal's Triangle
        int n = scanner.nextInt();
        // print Pascal's Triangle
        printTriangle(n);
    }

    /**
     * @param row rows in Pascal's Triangle
     * @param col columns in Pascal's Triangle
     * @return values in the Pascal's Triangle
     */
    private static int pascalTriangle(int row, int col) {
        if (col == 0 || col == row)
            // base case
            return 1;
        else
            // create the values in Pascal's Triangle
            return pascalTriangle(row-1, col-1) + pascalTriangle(row-1, col);
    }

    /**
     * @param n the input from the user, aka the n
     *          number of rows in Pascal's Triangle
     */
    private static void printTriangle(int n) {
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                System.out.println(pascalTriangle(row, col) + " ");
            }
            System.out.println();
        }
    }
}

标签： javaexceptionrecursionpascals-triangle

Answer 1

It seems your code is going into an infinite loop as you have a wrong condition for the inner loop. The inner loop is iterating and filling up the stack memory, eventually exceeding the amount allocated by the JVM.

In order to avoid this stack overflow error and and perfect the shape of your Pascal's Triangle you can simply add one extra loop and change the condition for the inner loop.

public static void printTriangle(int n) {
    for (int row = 0; row < n; row++) {
        //Added Spacer loop for getting perfect shape for pascal triangle
        for (int spacer = n; spacer > row; spacer--) {
            System.out.print(" ");
        }
        for (int col = 0; col <= row; col++) {
            System.out.print(pascalTriangle(row, col) + " ");
        }
        System.out.println();
    }
}