Блог

Главная - Вопросы по программированию - Рекурсивный метод вызывает java.lang.Ошибка StackOverflowError

Рекурсивный метод вызывает java.lang.Ошибка StackOverflowError

#java #exception #recursion #pascals-triangle

#java #исключение #рекурсия #паскали-треугольник

Вопрос:

Я пытаюсь создать треугольник Паскаля, а линия:

 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();
        }
    }
}

Комментарии:

1. Вам нужно использовать свой отладчик, чтобы увидеть, почему ваша рекурсия не останавливается там, где, по вашему мнению, она должна остановиться.

2. Второй вызов из printTriangle является pascalTriangle(0,1) , и второй рекурсивный вызов является pascalTriangle(-1,1) , затем второй рекурсивный вызов является pascalTriangle(-2,1) , затем pascalTriangle(-3,1) , затем pascalTriangle(-4,1) , затем pascalTriangle(-5,1) , затем pascalTriangle(-6,1) , затем …, затем StackOverflowError, — Я полагаю, что ваш второй цикл должен быть col<=row , а не col<n

Ответ №1:

Кажется, ваш код переходит в бесконечный цикл, поскольку у вас неверное условие для внутреннего цикла. Внутренний цикл повторяется и заполняет память стека, в конечном итоге превышая объем, выделенный JVM.

Чтобы избежать этой ошибки переполнения стека и улучшить форму вашего треугольника Pascal, вы можете просто добавить один дополнительный цикл и изменить условие для внутреннего цикла.

 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();
    }
}

Ответ №2:

Измените второй цикл на повторение до row , а не n до.

 public static void printTriangle(int n) {
    for (int row = 0; row < n; row  ) {
        for (int col = 0; col <= row; col  ) {
            System.out.print(pascalTriangle(row, col)   " ");
        }
        System.out.println();
    }
}