时间戳

首页 > 解决方案 > 在 JS 中使用递归的 Pascal 三角形 - 询问解释

javascript - 在 JS 中使用递归的 Pascal 三角形 - 询问解释

问题描述

我已经检查了其他主题。看起来这些问题主要涉及 C++ 和 Python 开发人员，但希望对递归有更好的理解。

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

        1
       1 1
      1 2 1
     1 3 3 1
    1 4 6 4 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);
    }
}

代码不绘制图表，而只返回三角形中最里面的值。

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

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

如果您愿意提供帮助，则可获得奖励：

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

标签： javascriptrecursionfunctional-programmingpascals-triangle

解决方案

让我们从一个相当笼统的解释开始，并在此过程中变得更具体，以便对递归有更好的直觉。递归是将问题分解为最小实例然后将这些实例一一组合以获得解决方案的策略。

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

0 + 0
0 + 1
1 + 0
1 + 1

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

我们还没有谈到递归算法的另一个重要特性：它们创建嵌套的计算结构。嵌套是递归所固有的。让我们可视化由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是可能的给定算法。

推荐阅读