logo标签列表

循环内的递归函数

javascript
5

我一直在学习递归函数，现在对它们有了大概的理解。当我在完成一个自由代码营的挑战时，遇到了这个问题，我不明白它的含义。在for循环中使用递归函数：

function steamroller(arr) {
   var newArr = [];

    for (var i = 0; i < arr.length; i++) {
       //If (i)th element is an array
       if (Array.isArray(arr[i])) {
          newArr = newArr.concat(steamroller(arr[i]));
          console.log(newArr);
       } else {
          newArr.push(arr[i]);
       }
   }
   return newArr;
}
steamroller([1, [2],[3, [[4]]]]);
//returns [1, 2, 3, 4]

我理解困难的那一句是：

newArr = newArr.concat(steamroller(arr[i]));

在这一行中，newArr与什么连接起来了？函数在.concat方法内再次被调用，是吗？但是那个for循环会发生什么呢？.concat方法内的函数调用会强制退出循环吗？
这里有一个JSFiddle，我已经将每个newArr记录到控制台，但我甚至无法跟随它。数组是这样构建的：
[1, 2]
[4]
[3, 4]
[1, 2, 3, 4] //Final

感谢您的选择。
3
如果arr的元素是一个数组，就对该数组进行递归调用。因此，newArr会连接到该元素数组（即arr[i]）上递归过程返回的结果。 - Hunan Rostomyan
2
看起来这是一种相当复杂的实现“flatten”的方式...我有什么遗漏吗？ - elclanrs
1
newArr.concat(steamroller(arr[i])); 将 newArr 与 steamroller(arr[i]) 进行拼接，并返回一个新的数组。这个新数组需要被赋值给一个变量以便使用。 - Nina Scholz
1
@elclanrs 是的，这就是练习的重点，“展平”数组。作为一名学生，这对我来说是一个新的表达方式。有没有更简单的方法来做到这一点？我不是在寻找简单的答案，我更愿意真正地学习。 - Chirpizard
5个回答
5
steamroller 函数需要遍历函数参数提供的数组中的索引，以确保查看数组的每个索引。
然而，原始数组具有多个索引，这些索引本身可能包含多个索引，所有这些索引都需要依次进行遍历。
调用 concat 仅在循环的当前索引上执行，这意味着结果是当前索引的“steamrollered”表示。
逐步操作如下：
1. 将原始数组传递给函数：[1, [2],[3, [[4]]]] 2. 循环从第一个索引开始：1，它不是数组，所以将其推送到结果数组中。 3. 下一个循环迭代的索引是[2]，它是一个数组，因此被递归调用。 4. 第一次对该递归函数进行调用接收到[2]并对其进行迭代。 5. 这个递归调用的第一次迭代发现索引为2，它不是数组，所以将其推送到结果数组中。 6. ...继续...
可以看出，当使用递归函数迭代嵌套数组时，我们总是得到内部整数值，无论嵌套多深。
谢谢。这非常有帮助！ - Chirpizard
1

首先输入：

steamroller([1, [2],[3, [[4]]]])

第一个元素不是数组，所以新数组 newArr 收到的是 '1'。 第二个元素是数组，因此它再次调用 steamroller 函数：

steamroller([1, [2],[3, [[4]]]])->steamroller(2)

它不是一个数组，因此它将元素连接到一个新数组中，所以它只是将2连接到一个空数组中。函数将返回它，并将[2]连接到包含[1]的newArr中，现在你有了[1,2]，控制台弹出了你在fiddle上看到的第一行。
我认为你已经明白了后面发生了什么，但你仍需要解释3和4发生了什么。
1

听起来你的思维混乱主要与"堆栈"的工作方式有关。

基本的函数调用会在调用点暂停执行，并逐步执行函数内的每一行代码，然后在函数外恢复执行。此外，你可以在其他函数中运行函数；这一点可能已经很清楚了。

重要的是要理解程序跟踪的所有内容。首先，程序会跟踪它被调用的位置，以便可以在堆栈中"弹出一个"并继续执行。例如，在执行的中间，堆栈可能如下所示（知道它所在的函数/行）：

steamroller:10
steamroller:8
steamroller:8
main:20

然后它当前的循环遇到了 "return" 关键字...
steamroller:8
steamroller:8
main:20

但这还不是全部-它还保留了在函数运行期间声明的每个变量实例。事实上，您可以拥有大约5、6或500万个newArr，因为这些变量是在堆栈上声明的，而不是在一个单一的位置上。
当进入函数时，其中的行号或实例变量等信息都不会被销毁-它只是保存在当前函数中，并通过内部函数进行步进。
有意义吗？
1
使用递归函数的问题是，控制台的返回结果会很混乱，因为它与普通循环不同，需要完成递归树的最后一个位置，然后才能返回控制台中的所有值。因此，如果您将数组的某个位置放在更深的位置（例如[[[[3]]]]），它将到达位置的末尾，然后返回所有值。因此，如果您在递归函数中添加某种控制台以查看其工作原理，则将收到某种树形结构，而不是像普通循环一样。这就是递归函数的危险之处，并且在生产服务器上，它们可能会对CPU使用率造成相当大的负担。因此，如果您可以通过执行任何递归函数来执行此操作，那么效果会更好。

因此，如果您更改代码为

 steamroller([1, [2],[3, [4]]]);
 //the return will be
 [1, 2]
 [3, 4]
 [1, 2, 3, 4]

谈到递归树中的层级，如果将[[3]]作为[[4]]放置，则返回结果将处于树的同一层级。

 steamroller([1, [2],[[3], [4]]]);
 //the return will be
 [1, 2]
 [3]
 [4]
 [3, 4]
 [1, 2, 3, 4]

你好，希望这能让你更好地理解递归函数。

谢谢，Felipe，这确实有帮助。你的第一句话帮了很大忙，我现在明白为什么console.log看起来如此不同，因为它从函数的两个不同实例中记录；第一次调用，然后是递归调用...我想是这样！:-) 感谢你的答案！ - Chirpizard
0

如果我们检查没有递归的运行，则：

i = 0 => arr[i] = 1 => newArr.push(arr[i]) => newArr = [1]
i = 1 => arr[i] = [2] => steamroller(arr[i]) = [2] => newArr = [1, 2]
i = 2 => arr[i] = [3, [[4]]] => steamroller(arr[i]) = [3, 4] => newArr = [1, 2, 3, 4]
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接