1

再帰関数はみんな知っていますよね？しかし、関数を再帰的にするのは正確には何ですか? 別の質問 ( JavaScript によるライトニング効果)のコメント セクションでちょっとした議論がありましたが、これは再帰関数に対する私の見方に異議を唱えるものでしたが、適切な定義が不十分であるという不満も残されました。

これまでの再帰関数の個人的な定義は次のとおりです。

直接的または間接的に自分自身を呼び出す場合、関数は再帰的です

注:以下の例では JavaScript コードを提供しますが、それらは非常に普遍的なものであると確信しています。

このような再帰関数の簡単な例は次のとおりです。

function a() {
    a();
}

しかし、これも：

function a() {
    b();
}

function b() {
    a();
}

またはこれさえ：

function a() {
    setTimeout(a, 1000);
}

これらの関数はどれも何も計算しませんが、自分自身を呼び出すという理由だけで再帰的であると考えていました。

思いついたことの 1 つは、3 番目の例は再帰的ではないということsetTimeoutです。また、 th 呼び出しから戻った後、nth 呼び出しに制御を返さないため、再帰的ではありませんn-1。

提起された別のポイントは、これらの関数はすべて再帰的な方法で実際の問題を計算しないため、再帰的ではないということでした。問題をより小さなインスタンスに分割して解決する必要があることを意味します。引用されたウィキペディアの記事は次のとおりです。

コンピューター プログラミングにおける再帰は、関数がそれ自体のより単純な、多くの場合小さいバージョンの観点から定義されている場合に例証されます。問題の解決策は、問題のより単純なバージョンから得られた解決策を組み合わせることによって考案されます。

したがって、これは再帰的です。

function fac(n) {
    if (n <= 0) {
        return 1;
    }
    return n * fac(n - 1);
}

しかし、これはそうではありません:

function fac(n) {
    if (n <= 0) {
        return 1;
    }
    console.log(n);
    fac(n - 1);
}

それでは、再帰関数の適切な定義は何ですか? まったくあるのでしょうか、それとも本当に単なる哲学的な問題なのでしょうか? 関数が再帰的であると分類されるためには、どのような機能が必要ですか?

4

4 に答える 4

2

再帰の定義? 理解できるまで、この行をもう一度読んでください。

(無限ループを防ぐための中止基準を持つ自己呼び出し関数)。

于 2013-07-17T08:54:56.380 に答える
2

再帰は、自分自身を呼び出す関数に付けられた名前です。関数が自分自身を無限に呼び出すかどうかに関係なく..それはまだ再帰です。

問題がサブ問題に分割されているとは限りません。ただし、コンピューターサイエンスでは。再帰という用語は、問題をサブ問題に分割することによって問題を解決するために使用される手法を指し、通常、問題は有限です。

もう 1 点、再帰は Stack を使用して実装されます。各関数呼び出しは、最後の呼び出しが基本条件に一致するまで、スタック内の他の呼び出しの上に積み上げられ、スタック内の関数は上から下に実行されます。

ただし、基本条件がない場合、または基本条件が満たされない場合。次に、関数への無限の呼び出しがスタックにプッシュされ、メモリがいっぱいになり、stackOverFlow 例外がスローされ、OS がプログラムを終了して処理します。

非同期setTimeout()呼び出しであり、再帰とは関係ありませんが、同じ関数が呼び出されているか別の関数であるかにかかわらず、呼び出し元の関数は呼び出された関数に依存しないため、独立した呼び出しです。

于 2013-07-17T09:15:44.297 に答える