帕斯卡三角形的递归

Question

我需要一些帮助来理解这个解决帕斯卡三角形递归函数的JavaScript代码。这段代码是针对LeetCode上的以下问题的解决方案：帕斯卡三角形

我不明白的地方是这行代码 newRow[i] = prevRows[numRows - 2][i - 1] + prevRows[numRows - 2][i];

我的猜测是我们正在将上面的两个元素相加以形成三角形底部的元素，这是显而易见的。但这是哪种数据结构？prevRows 是什么类型的？

另外，我在理解递归过程时遇到困难。似乎如果我输入一个数字比如5，这个函数就会自我调用4次，直到达到基本情况1，然后返回1。我不明白三角形是如何被构建出来的。

以下是代码：

var generate = function(numRows) {
    if (numRows === 0) {
        return [];
    }
    if (numRows === 1) {
        return [[1]];
    }
    
    let prevRows = generate(numRows - 1);
    let newRow = new Array(numRows).fill(1);
    
    for (let i = 1; i < numRows - 1; i++) {
        newRow[i] = prevRows[numRows - 2][i - 1] + prevRows[numRows - 2][i];
    }
    
    prevRows.push(newRow);
    return prevRows;
};

Martijn Pieters · Answer

有时候，如果清理一下代码并使用更有意义的变量名，会有所帮助。

function createPascalsTriangle(rowsCount) {
    if (rowsCount === 1) {
        return [[1]];
    }

    let previousTriangle = createPascalsTriangle(rowsCount - 1);
    let previousRow = previousTriangle[previousTriangle.length - 1];
    let newRow = [];

    newRow.push(1);

    for (let i = 0; i < previousRow.length - 1; i++) {
        newRow.push(previousRow[i] + previousRow[i + 1]);
    }

    newRow.push(1);

    return previousTriangle.concat([newRow]);
}

console.log(createPascalsTriangle(7).map(row => row.join(' ')));

这样是否更易于理解了呢？如果不的话，尝试一步一步在调试器中运行它，并观察变量的变化。

Stefan · Answer

当您提到“...然后它将返回1”时，并没有结束：每个递归调用都有返回值，因此不仅仅有一个返回[[1]]的情况；递归调用有多少次，就有多少次返回。并且每次调用都会返回一个二维数组（即金字塔形状），该数组比前一次执行的return多一行。

让我们通过一个例子来可视化这个过程，假设函数被传入参数3。下面的表格中，每一列代表一次函数执行过程，从左到右展开。当我们进行递归调用时，会移到右边一列，当执行return时，我们会回到左边相邻的一列。最右边的一列用来表示当前正在构建的二维数组，它从基本情况开始存在，并通过push调用不断扩展（所有局部的prevRows变量都引用同一个“增长中”的二维数组）：

| generate(3) | generate(2) | generate(1) | prevRows |
|----------------------|----------------------|------------------|---------------------|
| generate(2) | - | - | - |
|- | generate(1) | - | - |
| | | return [[1]] | - |
| | let prevRows = [[1]] | - | [[1]] |
| | let newRow = [1, 1] | - | [[1]] |
| | prevRows.push([1, 1]) | - | [[1], [1, 1]] |
| | return prevRows | - | [[1], [1, 1]] |
| let prevRows = [[1], [1, 1]] | - | - | [[1], [1, 1]] |
| let newRow = [1, 1, 1] | - | - | [[1], [1, 1]] |
| newRow[1] = 1 + 1 = 2 | - | - | [[1], [1, 1]] |
| prevRows.push([1, 2, 1]) | - | - | [[1], [1, 1], [1, 2, 1]] |
| return [[1], [1, 1], [1, 2, 1]] | - | - | [[1], [1, 1], [1, 2, 1]] |

希望这个示例能够帮您理解递归构建帕斯卡三角的过程。

gsm2009 · Answer

TablesAreCool left-aligned$1600 col 2 iscentered$12 col 3 isright-aligned$1