用于影响循环的递归变量

Question

我正在尝试使用递归来创建一个函数，该函数可以从帕斯卡三角形中的任何序列中获取任何项。基本上使用自然数作为第一个集合的加法序列，然后使用前一个集合作为加法序列，始终从1开始。单纯形

我目前正在学习JavaScript，并正在做我已经知道的Python中的工作，以测试JavaScript中的一些基本原理。然而，for循环似乎总是跳过一些数字。我认为发生的事情是，当函数调用自己并再次运行for循环时，它会影响函数中更高一级的变量I，导致它跳过序列中的一个数字。我不知道如何避免这种情况，因为JavaScript允许在同一范围内的函数中使用变量，这很有意义，但我不知道该如何避免。

var simplex = function(s,t){
if (s == 1){
return t
} else{
var n=1;
for (i = 1; i<t; i++){
n += simplex(s-1,t+1);
}
return n
}
}
console.log(simplex(3,3))

Answer 1

如果不为i声明作用域，它最终会在递归调用中持久化。您应该始终在必要的范围内声明这些。

这是一个清理版本：

function simplex(s,t){
if (s == 1){
return t
}

let n = 1;

for (let i = 1; i < t; i++){
n += simplex(s-1, t+1);
}

return n;
}
console.log(simplex(3,3));

由于现在是2020年，并且let和const得到了广泛支持，因此建议优先使用这些样式，而不是旧的var样式，因为旧样式具有不同的作用域考虑因素。let的范围要窄得多，与预期的匹配度也要高得多。

作为一种习惯，你应该努力以的形式编写循环

for (let i = 0; ...)

let明显存在的地方。这表明迭代变量仅在for循环中具有相关性。

Answer 2

在javascript中，变量具有函数作用域。

正如@Barmar在评论中所说，问题出在这一行：

for (i = 1; i<t; i++)

如果您键入

for(var i = 1; i<t; i++)

那么您在这个函数中声明了一个新的变量i，您的问题就解决了。

当您在javascript:中键入类似内容时

i = 1;

如果尚未声明i，则将隐式创建一个变量i，并将其分配给全局window对象。

你可以用这个简单的代码来演示它：

i = 7;
console.log(`window.i = ${window.i}`);

Answer 3

其他人指出了一个未声明变量的简单问题。

但即使在修复之后，仍然存在三个逻辑错误。您没有在循环中使用循环变量i。虽然有时这是可以的，但它不在这里。您需要将其作为simplex的参数。第二，你的循环边界很短。您需要上一列的t条目，但通过测试i < t，您可以停止使用t - 1st条目。最后，用1开始累积(n(。总和应从0开始累加。修复这些问题，我们有一个工作功能，看起来像这样：

const simplex = function(s, t) {
if (s == 1) {
return t
} else {
var n = 0;
for (let i = 1; i <= t; i++){
n += simplex(s - 1, i)
}
return n
}
}

添加一些日志记录语句来显示流程，我们可以得到：

const simplex = function (s, t, d = 0) {
console.log('|   '.repeat(d) + `simplex (${s}, ${t})`)
if (s == 1) {
console.log('|   '.repeat(d) + ``+-> ${t}`)
return t
} else {
var n = 0;
for (let i = 1; i <= t; i++){
n += simplex (s - 1, i, d + 1)
}
console.log('|   '.repeat(d) + ``+-> ${n}`)
return n
}
}
simplex (3, 3) //=> 10

.as-console-wrapper {max-height: 100% !important; top: 0}

simplex (3, 3)
|   simplex (2, 1)
|   |   simplex (1, 1)
|   |   `+-> 1
|   `+-> 1
|   simplex (2, 2)
|   |   simplex (1, 1)
|   |   `+-> 1
|   |   simplex (1, 2)
|   |   `+-> 2
|   `+-> 3
|   simplex (2, 3)
|   |   simplex (1, 1)
|   |   `+-> 1
|   |   simplex (1, 2)
|   |   `+-> 2
|   |   simplex (1, 3)
|   |   `+-> 3
|   `+-> 6
`+-> 10

但我相信这个功能可以在很多方面得到简化。有一些简单的事情，比如将else块移到根，并使用箭头函数代替函数表达式。在我看来，更重要的是使用像sum这样的辅助函数来合计多个值，而不是将该逻辑包含在该函数中。通过还包括countTo，它只返回第一个n计数，我们可以使用map，使代码更具声明性。所以我可能更喜欢这样的版本：

const countTo = (n) => n < 1 ? [] : [...countTo (n - 1), n]
const sum = (xs) => xs .reduce ((a, b) => a + b, 0)
const simplex = (s) => (t) =>
s == 1
? t
: sum (countTo (t) .map (simplex (s - 1)))
console .log (simplex (3) (3))

此版本还对API进行了一次更改。这个函数不是采用单纯形数和项并返回值的函数，而是采用单纯形数并返回函数，该函数采用项并返回该值。这意味着将其称为simplex (s) (t)而不是simplex (s, t)。做到这一点并不难，而且它有很多好处。但将其转换为其他格式非常容易，只会给实现增加很小的复杂性。

---

更新

我忘了提到我的第一种方法，那就是将单纯形数视为直接进入Pascal三角形的索引。Pascal三角形包含二项式系数，可以用简单的递归choose (n, k) = choose (n, k - 1) + choose (n - 1, k - 1)计算，有一些简单的基本情况。

据此，simplex (s, t)就是choose (s + t - 1, t)。它可能看起来像这样：

const choose = (n, k) =>
k == 0
? 1
: n == 0
? 0
: choose (n - 1, k) + choose (n - 1, k - 1)
// Ex: choose (7, 3) //=> 35
console .log ('Pascal Triangle:n');
console .log (
Array .from (
{length: 9}, 
(_, n) => Array .from ({length: n + 1}, (_, r) => choose (n, r))
).map (
r => r .map (n => `${n}`.padStart(2, ' ')) .join (' ')
) .join ('n') + 'n ...'
)
const simplex = (s, t) => 
choose (s + t - 1, t)

console.log ('simplex (3, 3): ', simplex (3, 3))

.as-console-wrapper {max-height: 100% !important; top: 0}