在 JS 中使用递归的帕斯卡三角形 - 询问的解释

Question

我查看了其他主题。看起来这些问题主要与 C++ 和 Python 开发人员有关，但想询问对递归有更好的理解。

帕斯卡三角形是由边上的 1 和内部的上面两个数字之和组成的三角形：

代码如下：

function pascalTriangle(row, col) {
    if (col === 0) {
        return 1;
    } else if (row === 0) {
        return 0;
    } else {
        return pascalTriangle(row - 1, col) + pascalTriangle(row - 1, col - 1);
    }
}

代码不画图，只画 returns 三角形中最里面的值。

我的问题是关于递归else语句：

调用栈是如何执行else语句的？该行背后的逻辑实际上是什么？

乐于助人的加分项:

完成特定行的执行后，如何让您的代码移动到下一行？

Answer 1

这似乎有效

function buildTriangle(rows) {
 let result = []
 for(let row = 0; row < rows; row++){
   let rowData = []
   for(let col = 0; col <= row; col ++){
     rowData.push(pascalTriangle(row, col))
   }
   result.push(rowData)
 }
  return result;
 }



function pascalTriangle(row, col) {
    if (col === 0) {
        return 1;
    } else if (row === 0) {
        return 0;
    } else {
        return pascalTriangle(row - 1, col) + pascalTriangle(row - 1, col - 1);
    }
}
console.log(buildTriangle(6).join('\n'))

你post的函数只是计算位置(row,col)上元素的值
正如您可能已经知道的那样，可以将上面一行中的两个数字相加来计算值，并且上面行中的数字是使用上面一行中的数字等计算的
所以这就是为什么这个函数作为递归

Answer 2

让我们从一个相当笼统的解释开始，然后再进行更具体的解释，以获得对递归更好的直觉。递归是一种将问题分解成最小的实例，然后将这些实例一个一个地组合起来以获得解决方案的策略。

给定问题的最小实例是什么？ 0 和 1，因为它们是由两个基本案例返回的。每个递归步骤最终都会产生这些基本情况之一。由于我们有两个不同的递归步骤 pascalTriangle(row - 1, col) 和 pascalTriangle(row - 1, col - 1)，因此可能有以下排列：

这些操作代表给定问题的最小实例。请注意，您可以用基本案例替换递归步骤，但您得到的只是递归算法的快照。大局有点复杂。

我们还没有谈到另一个重要的属性递归算法：它们创建嵌套的计算结构。嵌套是 recurison 所固有的。让我们想象一下 pascalTriangle 创建的嵌套结构。我们可以通过替换手动执行此操作，也可以通过调整函数自动执行此操作：

function pascalTriangle(row, col) {
    if (col === 0) {
        return 1;
    } else if (row === 0) {
        return 0;
    } else {
        return `(${pascalTriangle(row - 1, col)} + ${pascalTriangle(row - 1, col - 1)})`;
    }
}

console.log(pascalTriangle(4, 2));
// ((((0 + 0) + (0 + 1)) + ((0 + 1) + 1)) + (((0 + 1) + 1) + 1))

这是一个合成的嵌套结构，相当于你的递归计算实际创建的中间结构。如果你把它加起来，你会得到 6，这是预期的结果。

也许你已经注意到我上面列出的排列是错误的。对于给定的算法，只有 0 + 0 和 0 + 1 是可能的。

在 JS 中使用递归的帕斯卡三角形 - 询问的解释

Pascal's Triangle with Recursion in JS - Explanation Asked

javascript

recursion

functional-programming

pascals-triangle