正確理解遞歸的方法（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));