帕斯卡三角递归Javscript

Question

我需要一些帮助来理解 JavaScript 中帕斯卡三角形递归函数的解决方案。这段代码是LeetCode上以下问题的解决方案：https://leetcode.com/problems/pascals-triangle/

我不明白的是这条线

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

Answer 1

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

function makeTriangle(size) {
    if (size === 1) {
        return [[1]];
    }

    let smallerTriangle = makeTriangle(size - 1);
    let lastRow = smallerTriangle.at(-1);
    let newRow = [];

    newRow.push(1);

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

    newRow.push(1);

    return smallerTriangle.concat([newRow]);
}

console.log(makeTriangle(7).map(String))

这样你是不是更容易理解了？如果没有，请尝试在调试器中逐步运行它并观察变量。

Answer 2

你写：”...然后它会返回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]]

我希望这能澄清这一点。