打印帕斯卡三角形的更多递归方法

Question

我将尝试使用递归方法将帕斯卡三角形打印到标准输出。我从创建一个迭代方法开始，以了解我希望该方法如何工作。请参阅下面的代码。

/**
 * Print Pascal's triangle with PrintOut.
 *
 * @param n The amount of rows in total
 */
public static void printPascal(int n) {
    for (int i = 0; i < n; i++) {
        System.out.format("%" + (n - i) * 3 + "s", "");
        for (int j = 0; j <= i; j++) {
            System.out.format("% 6d", binom(i, j));
        }
        System.out.println();
    }
}

Javadoc 和 binom 的签名

/**
 * Method which calculates the values in Pascal's triangle.
 *
 * @param n The row of "the place"
 * @param k The column of "the place"
 * @return A value on "the place" from the triangle
 */
public static int binom(int n, int k)

然后我开始研究递归方法。我不能使用任何 class 变量进行打印 - 所以我不能使用矢量。我不能有任何对象，方法在 class 中，这两个方法和 main 是我唯一可以实现的方法。最大的问题是我无法保存 binom 应该使用的变量，因为它们在每次迭代后都会重置。现在我有了 printPascal 的代码：

if (n < 0) {
    return;
}
printPascal(n - 1);
for (int k = 0; k <= n; k++) {
    System.out.format("%6d", binom(n, k));
}
System.out.println();

有没有办法使上面的方法更具递归性 - 有没有办法去掉 for 循环？

Answer 1

希望对您有所帮助？

public class PascalTriangle {
    public static void main(String[] args) {
        printPascal(5);
    }

    private static void printPascal(int i) {
        auxPrintPascal(0, i);
    }

    private static void auxPrintPascal(int row, int numOfRows) {
        if (row > numOfRows) {
            return;
        }
        printPascalTriangleRow(row, 0);
        System.out.println();
        auxPrintPascal(row + 1, numOfRows);
    }

    private static void printPascalTriangleRow(int row, int col) {
        if (col > row) {
            return;
        }
        System.out.print(binomial(row, col) + " ");
        printPascalTriangleRow(row, col + 1);
    }

    private static long binomial(int n, int k) {
        if (k > n - k)
            k = n - k;

        long b = 1;
        for (int i = 1, m = n; i <= k; i++, m--)
            b = b * m / i;
        return b;
    }
}

如果你坚持，这应该行吗？

private static void sillyPrintPascal(int row, int col, int numOFRows) {
    if (row > numOFRows) {
        return;
    }
    if (col > row) {
        return;
    }
    System.out.print(binomial(row, col) + " ");
    if (col == row) {
        System.out.println();
        sillyPrintPascal(row + 1, 0, numOFRows);
    } else {
        sillyPrintPascal(row, col + 1, numOFRows);
    }
}

打印帕斯卡三角形的更多递归方法

More recursive method to print Pascal's triangle

java

algorithm

recursion

pascals-triangle