フィボナッチ再帰関数の「働き」は？

質問

私はJavascriptの初心者で、それを読んでいるときに、関数の再帰について説明した章にたどり着きました。 それはフィボナッチ数列のn番目の数を見つけるために、例の関数を使用していました。 コードは次のとおりです。

function fibonacci(n) {
    if (n < 2){
        return 1;
    }else{
        return fibonacci(n-2) + fibonacci(n-1);
    }
}

console.log(fibonacci(7));
//Returns 21

この関数が何をしているのか、正確に把握することができません。 誰かここで起こっていることを説明できますか？ 5行目で、関数が自分自身を呼び出すところで行き詰っています。 ここで何が起こっているのでしょうか？

どのように解決するのですか？

関数を自分自身の観点から定義していますね。一般的には fibonnaci(n) = fibonnaci(n - 2) + fibonnaci(n - 1) . この関係をコードで表現しているだけです。ですから fibonnaci(7) を観察することができます。

• fibonacci(7) は fibonacci(6) + fibonacci(5)
• fibonacci(6) は fibonacci(5) + fibonacci(4)
• fibonacci(5) は fibonacci(4) + fibonacci(3)
• fibonacci(4) は fibonacci(3) + fibonacci(2)
• fibonacci(3) は fibonacci(2) + fibonacci(1)
• fibonacci(2) は fibonacci(1) + fibonacci(0)
• fibonacci(1) は 1 に等しい
• fibonacci(0) は 1 に等しい

を評価するために必要なパーツがすべて揃いました。 fibonacci(7) を評価するのに必要なパーツがすべて揃いました。注目すべきは 基本ケース -- return 1 いつ n < 2 -- はこれを可能にするものです。これは再帰を停止させ、スタックを展開して各ステップで返している値を合計する処理を開始できるようにするものです。このステップがなければ fibonacci を呼び続け、最終的にプログラムがクラッシュしてしまいます。

これを説明するいくつかのロギングステートメントを追加するのに役立つかもしれません。

function fibonacci(n, c) {
    var indent = "";
    for (var i = 0; i < c; i++) {
        indent += " ";
    }
    console.log(indent + "fibonacci(" + n + ")");
    if (n < 2) {
        return 1;
    } else {
        return fibonacci(n - 2, c + 4) + fibonacci(n - 1, c + 4);
    }
}

console.log(fibonacci(7, 0));

出力します。

fibonacci(7)
    fibonacci(5)
        fibonacci(3)
            fibonacci(1)
            fibonacci(2)
                fibonacci(0)
                fibonacci(1)
        fibonacci(4)
            fibonacci(2)
                fibonacci(0)
                fibonacci(1)
            fibonacci(3)
                fibonacci(1)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
    fibonacci(6)
        fibonacci(4)
            fibonacci(2)
                fibonacci(0)
                fibonacci(1)
            fibonacci(3)
                fibonacci(1)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
        fibonacci(5)
            fibonacci(3)
                fibonacci(1)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
            fibonacci(4)
                fibonacci(2)
                    fibonacci(0)
                    fibonacci(1)
                fibonacci(3)
                    fibonacci(1)
                    fibonacci(2)
                        fibonacci(0)
                        fibonacci(1)

同じインデントレベルの値は、前のインデントレベルの結果を生成するために合計されます。