「javascript言語精粋」学習ノート-再帰関数

再帰関数とは、直接または間接的に自身を呼び出す関数のことです.再帰的には、強力なプログラミング技術であり、それは同じようなサブ問題のセットに分解され、それぞれが通常の解で解決されます.一般的には、再帰関数は、自身を呼び出してその問題を解決する.
本の中の小さな例「ハノータ」.塔には3本の柱と直径が異なる中空ディスクがあります.最初は源柱のすべての円盤が小さい時から大きな順に積み重なっています.目的は、円盘を他の柱に移动するたびに、目的の柱に円盘の山を移动させ、大きな円盘を小さな円盘に置いてはいけないということです.

 var hanoi = function(disc, src, aux, dst){
    if (disc > 0) {
        hanoi(disc - 1, src, dst, aux);
        document.writeln('Move disc' + disc + ' form ' + src + ' to ' + dst);
        hanoi(disc - 1, aux, src, dst);
    }
};

hanoi(3, 'src', 'aux', 'dst');

実行コードの結果:

Move disc1 form src to dst
Move disc2 form src to aux
Move disc1 form dst to aux
Move disc3 form src to dst
Move disc1 form aux to src
Move disc2 form aux to dst
Move disc1 form src to dst

hanoi関数は、ディスクの山を一つの柱から別の柱に移動させるためには、補助的な柱を使用する必要があります.この問題を3つの小さな問題に分割します.まず、円盤の中の小さな円盤を補助柱に動かして、下の大きな円盤を露出させ、下の円盤を目標柱に移動させます.最後に、彼は先ほどの小さな円盤を補助柱から目標柱に移動しました.それらの問題は、円盤の移動を自分自身で処理することで解決されます.

がhanoiの関数に伝達するパラメータは、現在移動しているディスクの番号と、それが使用する3本の柱を含む.自身を呼び出して、現在処理されている円盤の上の円盤を処理します.最後に、彼は存在しない円盤の番号を呼び出します.このような状況では、彼は何の操作も実行しない.この関数は不正を無視しているので、死のサイクルの問題も心配しなくても大丈夫です.

本の第二の例は、再帰関数は、DOMなどのツリー構造を非常に効率的に動作させることができるということである.再帰的呼び出しは、指定されたツリーの一部を処理することである.

//            ，   HTML                。
var walk_the_DOM = function(node, func){
    func(node);
    node = node.firstChild;
    while (node) {
        walk_the_DOM(node, func);
        node = node.nextSibling;
    }
};

//     walk_the_DOM   ，                   。
//                  。
var getElementsByAttribute = function(att, val){
    var results = [];

    walk_the_DOM(document.body, function(node){
        var actual = node.nodeType === 1 && node.getAttribute(att);
        if (typeof actual === 'string' && (actual === val || typeof value 
            != 'string')) {
            results.push(node);
        }
    });

    return results;
};

いくつかの言語は後戻りの最適化を提供しています.これは、関数が再帰的な結果を返すと、呼び出されたプロセスがサイクルに置き換えられ、速度が上がることを意味している.残念ながら、jsには最終的な再帰的な最適化がない.
幸運なことに、ES 6は私達に最後の再帰を持ってきて、詳しくECMAScript 6を迎えて、最後を使って再帰します.どんな場合に再帰を使いますか?