何が再帰であり、なぜそれを使用しないでください?

再帰とは何か
関数は、関数自体を呼び出すときだけです.これは、いくつかの関数を書くことがはるかに簡単です.私たちはfactorial ファンクション

function factorial(number) {
    if (number == 1)
        return 1;
    return number * factorial(number - 1);
}

またはFibonacci sequence

function fib(number) {
    if (number == 0 || number == 1)
        return number;
    return fib(number - 1) + fib(number - 2)
}

または再帰的にツリーを横断することができます

function traverse(rootNode) {
    if (rootNode != null) {
        traverse(rootNode.left);
        traverse(rootNode.right);
        doSomethingWith(rootNode);
    }
}
// called like traverse(someTree.root)

リストとファイルシステムだけでなく、私は今すぐに取得するよりも少し複雑であり、factorial/fibonacci/ツリーは、このデモに十分です.

なぜそれを使用しないでください?
再帰の最も単純な問題は副問題の繰り返しです計算fib(10) 計算が必要ですfib(9) and fib(8) , でも計算fib(9) 必要fib(8) and fib(7) , それは既に不快な繰り返しです.実際には、そのような機能を計るならば(あなたはそれを行うべきではありません、それは愚かな方法です、しかし、それはこのデモのために働きます)

var numberOfCalculations = new Array(11).fill(0);
function fib(number) {
    numberOfCalculations[number]++;
    if (number == 0 || number == 1)
        return number;
    return fib(number - 1) + fib(number - 2);
}
fib(10);
console.table(numberOfCalculations);

あなたは、我々が効果的に計算fib(1) ちょうど10回フィボナッチ数を得るために55回.あなたがそのテストをするならばfib(20) , 明らかに計算が必要fib(1) 6700倍以上.それは明らかに恥ずかしいほど効率が悪い.
つ目の問題は実装の問題です.ほとんどのコンピュータと言語はcall stack , コンピュータが言う前にfactorial(10) , 計算する必要がありますfactorial(9) , だから私はfactorial(10) スタックの後に計算して作業するfactorial(9) . できる前にfactorial(9) , する必要があるfactorial(8) , so factorial(9) “スタックに行く”などのようにヒットするまでfactorial(1) , それが最終的に実際の結果を返すことができて、計算を再開するときfactorial(2/3/4/5/etc) . 計算するfactorial(10) スタックには、非常に有限のサイズを持つスタック9中間計算を置く必要があります.あなたはそれを得ることができますfactorial(10) , そしてfactorial(100) , でもfactorial(1000) ブラウザをクラッシュさせるか、少なくともスタックオーバーフローエラーをスローします.
さらに、再帰的な解決は、しばしば、スタックのプッシュとポップを行う処理コストのために、比較的反復ソリューションよりも遅くなりますが、プロファイリングを除いて、それは実証するのが難しいです.

それはどうしますか.
最初に、あなたは実際にそれについて何かを行う必要があることを確認します.早めの最適化は結局すべての悪の根源です.遅い場合でも、再帰は通常、ほとんどの目的のために十分に速いです.あなたが再帰が問題であると決定したならば、それを解決することに進んでください.
「最も単純な」解決は、再帰的なものの代わりに反復解決をするだけです.ここでの基本的な考え方は、プログラム呼び出しスタックを自分の明示的なスタックに置き換えることです.

function traverse(rootNode) {
    const stack = [];
    stack.push(rootNode);
    while (stack.length > 0) {
        const currNode = stack.pop();
        if (currNode != null) {
            // Note that we reverse the order of the push, so node.left gets popped and processed before node.right 
            stack.push(currNode.right);
            stack.push(currNode.left);
            doSomethingWith(currNode);
        }
    }
}

いくつかの場合では、for - whileループに直接スタックをスキップすることで得ることができます.

function factorial(number) {
    let accumulator = 1;
    for (let ii = number; ii >= 1; ii--) {
        accumulator *= ii;
    }
    return accumulator;
}
//Or, more cleanly
function factorial(number) {
    let accumulator = 1;
    for (let ii = 1; ii <= number; ii++) {
        accumulator *= ii;
    }
    return accumulator;
}

もう一つのオプションはmemoize あなたが再利用のための高価な計算の結果を格納する関数.これは時間のためにスペースをトレードする明白なトレードオフを運びます、しかし、それはしばしば良い考えです.

function fib(number) {
    var memoize = [];
    return fibrec(number, memoize);
}
function fibrec(number, memoize) {
    if (memoize[number] != null)
        return memoize[number];

    if (number == 0 || number == 1)
        return number;
    const result = fibrec(number - 1, memoize) + fibrec(number - 2, memoize);
    memoize[number] = result;
    return result;
}

また、私のお気に入りの愚かなFibonacciメソッドの2つのメソッドを組み合わせることができます.

function fibiter (number) {
    const memoize = [0, 1];
    for (let ii = 2; ii <= number; ii++) {
        memoize[ii] = memoize[ii-1] + memoize[ii-2];
    }
    return memoize[number];
}

つ目のオプションは、実装依存であり、いくつかの言語でのみ使用可能ですtail-call optimization . 再帰的な呼び出しが返す前に実行される最後のものであるので、これは機能を書いています.そして、それは我々が呼び出し状態を保存する必要はないことを意味します.The factorial 記事の前に示される関数は、呼び出し元の関数がまだしなければならないので、最適化されたtail callではありませんnumber * factorial(number - 1); , これは呼び出し関数がスタックに格納されなければならないことを意味します.

function factorial(number) {
    return factorial_TCO(number, 1);
}
function factorial_TCO(number, accumulator) {
    if (number == 1)
        return accumulator;
    return factorial_TCO(number - 1, number * accumulator);
}

結論
再帰は非常に強力なツールですが、その危険性を認識する必要がありますどのようにそれらを軽減する.