再帰を適切に理解する方法（JavaScript）

Question

私は再帰を理解しようとしていますが、わかりやすい方法で直感的に理解していますが、返されるデータの集約は苦労します。

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 ]

結構です

は例えば、配列を平らにするために、JavaScriptで私は、次のコードを思いつきましたすべてがグローバル変数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 ]

まず、私は2つの異なる平坦化の手続きを行って表示されます。 1つのレベルの入れ子をフラット化するために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

グローバル変数の代わりに（より適切な再帰を行うために）、flatten関数の引数としてgを送信し、変更されたgをreturn文で渡すことができます。

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));