正确理解递归的方法（javascript）

Question

我试图理解递归，并且我对它的直观工作方式有一些体面的理解，但是返回的数据的聚合是我努力的一点。

例如，在JavaScript的扁平化阵列，我想出了下面的代码：

var _flatten = function(arr){ 
    if(!arr instanceof Array) return arr; 
    var g = []; 

    function flatten(arr){ 

    for(var i = 0; i < arr.length;i++){ 
     if(arr[i] instanceof Array){ 
     flatten(arr[i]); 
     }else{ 
     g.push(arr[i]); 
     } 
    } 
    } 

    flatten(arr); 
    return g; 
} 

谈到这样

var list = [1,2,3,4,5,6,[1,2,3,4,5,[1,2,3],[1,2,3,4]]]; 

事成这样：[ 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 1, 2, 3, 1, 2, 3, 4 ]

这很好和所有，但全球变量g似乎是某种廉价的黑客。我不知道如何去思考当到达堆栈顶部时返回的结果以及将函数传回堆栈的结果。你将如何实现这个功能，以及如何更好地掌握这个功能？

谢谢！

Answer 1

有many ways to write an array flattening procedure，但我明白你的问题是关于一般

的g理解递归是不是在这个词的任何感全球性的，但它是一个执行选择的症状。突变不一定是坏的，只要你保持它的本地化你的功能 - 该g永远不会泄漏的功能之外，有人可能会观察到副作用。

就我个人而言，我认为最好是将问题分解为小型通用程序，这样可以更容易地描述代码。

你会注意到我们不需要设置像g这样的临时变量，或者处理像i这样的递增数组迭代器 - 我们甚至不需要查看数组的.length属性。不必考虑这些事情，以声明的方式编写我们的程序非常好。

// concatMap :: (a -> [b]) -> [a] -> [b] 
 
const concatMap = f => xs => xs.map(f).reduce((x,y) => x.concat(y), []) 
 

 
// id :: a -> a 
 
const id = x => x 
 

 
// flatten :: [[a]] -> [a] 
 
const flatten = concatMap (id) 
 

 
// isArray :: a -> Bool 
 
const isArray = Array.isArray 
 

 
// deepFlatten :: [[a]] -> [a] 
 
const deepFlatten = concatMap (x => isArray(x) ? deepFlatten(x) : x) 
 

 
// your sample data 
 
let data = [0, [1, [2, [3, [4, 5], 6]]], [7, [8]], 9] 
 

 
console.log(deepFlatten(data)) 
 
// [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ] 
 

 
console.log(flatten(data)) 
 
// [ 0, 1, [ 2, [ 3, [ 4, 5 ], 6 ] ], 7, [ 8 ], 9 ]

首先你会看到我做了两个不同的扁平化的过程。 flatten来压扁一层嵌套，并且deepFlatten压扁任意深度的数组。

您还会看到我使用Array.prototype.map和Array.prototype.reduce，因为它们是由ECMAScript提供的，但这并不意味着您仅限于使用您拥有的程序。您可以制定自己的程序填补空白。在这里，我们制作了concatMap，这是一个由其他语言如Haskell提供的有用的泛型。

利用这些仿制药，你可以看到deepFlatten是一个非常简单的过程。

// deepFlatten :: [[a]] -> [a] 
const deepFlatten = concatMap (x => isArray(x) ? deepFlatten(x) : x) 

它是由一个单一的表达，包括拉姆达由单一if分支（通过使用三元运算?:的）

---

也许这是很多参加，但希望它表明“编写一个递归过程”并不总是关于状态变量的复杂设置和控制递归的复杂逻辑。在这种情况下，这是一个简单的

if (condition) recurseelsedon't

如果您有任何问题，请告诉我。我很高兴以任何方式帮助你。

Answer 2

而不是一个全局变量（为了使它更适合递归），你可以用g作为参数发送给flatten函数，然后用return语句传回修改过的g。

var _flatten = function(arr) { 
    if (!arr instanceof Array) return arr; 

    function flatten(arr, g) { 
    for (var i = 0; i < arr.length; i++) { 
     if (arr[i] instanceof Array) { 
     flatten(arr[i], g); 
     } else { 
     g.push(arr[i]); 
     } 
    } 
    return g; 
    } 

    return flatten(arr, []); 
} 

Answer 3

实际上，递归编码非常简单，它的每个方面都应包含在函数体中。任何需要通过的信息都应通过参数发送到下一个递归。全球性东西的使用是非常丑陋的，应该避免。相应地，我会简单地进行如下的阵列展平工作：

var list = [1,2,3,4,5,6,[1,2,3,4,5,[1,2,3],[1,2,[9,8,7],3,4]]]; 
 

 
function flatArray(arr){ 
 
    for (var i = 0, len = arr.length; i < len; i++) 
 
    Array.isArray(arr[i]) && (arr.splice(i,0,...flatArray(arr.splice(i,1)[0])), len = arr.length); 
 
    return arr; 
 
} 
 

 
console.log(flatArray(list));