JavaScriptによる再帰を理解する

いくつかの問題は再帰に適しています。たとえば、フィボナッチシーケンスなどのシーケンスには再帰的な定義があります。シーケンス内の各数値は、シーケンス内の最初の2つの数値の合計です。ツリーデータ構造で構築または移動する必要がある問題も、再帰によって解決することができます。再帰的に考えるために自分自身を訓練することは、そのような問題を解決するための強力なスキルをあなたに与えます。

このチュートリアルでは、いくつかの再帰関数がどのように機能するかを段階的に説明し、再帰関数を体系的に定義するためのいくつかの手法を示します。

コンテンツ：

• 再帰とは何ですか？
• デジタル再帰
• 再帰をリストします
• リストを作成します
• 尾の再帰
• 要約します

再帰とは何ですか？

再帰的に定義された関数は、単純化されたバージョン自体によって定義される関数です。ここに簡略化された例があります：

関数doa（n）{
    // ...
    if（n> 0）{
        DOA（N-1）;
    }
}

再帰の仕組みを概念的に理解するために、コードに依存しない例を調べます。会社からの電話に応答する責任があるとします。これは忙しい会社なので、あなたの電話は複数の電話回線を持っているので、複数の電話を同時に処理できます。各電話回線には携帯電話にボタンがあり、着信が発生すると点滅します。今日、仕事に行って電話をオンにすると、4行が同時に点滅します。したがって、すべての呼び出しに応答し始めます。

あなたは最初の行を拾って、「待ってください」と言います。次に、3行目をピックアップして、スタンバイなどに置きます。最後に、各コールが終了したら、前の発信者に戻り、その呼び出しを完了して電話を切ります。

この例の各呼び出しは、関数の再帰呼び出しに似ています。通話を受けると、コールスタックに（コード内）に配置されます。すぐに通話を完了できない場合は、スタンバイをします。関数呼び出しがすぐに計算できない場合、コールスタックに残ります。通話に答えることができれば、それは拾われます。コードが関数呼び出しを計算できるようになると、スタックから飛び出します。次のコードの例を見るときは、この比phorを覚えておいてください。

デジタル再帰

すべての再帰関数には、終了できるように基本的なケースが必要です。ただし、機能にベースケースを追加するだけでは、無限に実行されないようにしません。この関数には、基本的な状況に近づくためのステップが必要です。これが再帰的なステップです。再帰ステップでは、問題は問題の小さなバージョンに縮小されます。

nから始まるすべての数値を掛ける関数があるとします。これは因子関数と呼ばれ、nが1に等しい場合は4！として記述します。

各ステップでは、現在の数値から1を差し引きます。再帰的な状況は何ですか？再帰的なケースは関数の事実です（4）。

16. 4は1に等しいですか？いいえ。事実を置く（3）。
17. 3は1に等しいですか？いいえ。事実を置く（2）。
18. 2は1に等しいですか？いいえ。事実を置く（1）。
19. 1は1に等しいですか？はい。事実（2）を返し、2を返します。
20. 取得3 * fact（2）はfact（4）であり、24を返します。

関数が各呼び出しを処理する方法を確認する別の方法を次に示します。

 <code>fact(4) 4 * fact(3) 4 * ( 3 * fact(2) ) 4 * ( 3 * ( 2 * fact(1) )) 4 * ( 3 * ( 2 * 1 ) ) 4 * ( 3 * 2 ) 4 * 6 24</code>

再帰的な場合、パラメーターが変更され、基本的なケースに近づく必要があります。このパラメーターは、基本的な場合にテストする必要があります。前の例では、再帰ケースで1を減算するため、基本的な場合には、パラメーターが0に等しいかどうかをテストします。

チャレンジ

1. 再帰的ではなくループを使用して合計関数を実装します。
2. 2つの数値を再帰的に乗算する関数を作成します。たとえば、0;
3. フィルター機能を簡素化して、リストからすべてのアイテムを削除します。たとえば、["a"、 "b"、 "d"]。

尾の再帰

テールの再帰は、コンパイラがテールコールオプティメーション（TCO）を実行して、通常の再帰の多くのパフォーマンス欠陥を防ぐことを可能にする再帰の一種です。さらに、テールの再帰は、関数呼び出しの最大深度の問題を解決します。ただし、機能を機能させるには、何らかの形で機能を記述する必要があります。

尾の再帰は、関数の終わりに再帰関数を呼び出す関数に適しています。たとえば、ここでは、sum（）関数のテール再帰バージョンです。Sum（）の返品値全体が戻り値全体であるため、ランタイムは外部関数を安全に破棄し、内部関数の結果のみを返すことができます。しかし、多くの人がこのようなことを旅します：

 function nottailRecursive（n）{
    // ...
    NotTailRecursive（n）1を返します
}

再帰関数は最後に呼び出されるため、これは尾の再帰を使用すると思うかもしれません。しかし、そうではありません。これは、JavaScriptが外部関数に戻って1を追加する必要があるためです。あなたがそれを書き直す方法の1つは、 1引数に渡すことです。そうすれば、内部関数がその計算を行うことができます。

現在、すべてのブラウザがテールコールの最適化をサポートしているわけではありませんが、それはES標準であるため、将来的にはより多くのサポートが見られる可能性があります。さらに、通常は関数パラメーターへの変化を分離するため、通常は良い実践です。

チャレンジ

この記事の例の再帰関数を尾の再帰関数に再構築します。

要約します

再帰関数には3つの部分があります。 1つ目は、終了条件である基本的な状況です。 2つ目は、基本的な状況に近づくステップです。 3番目は再帰ステップで、関数は単純化された入力でそれ自体を呼び出します。

再帰は反復のようなものです。再帰的に定義するか、ループを使用して定義できる機能。再帰を使用する際に考慮すべきその他のことには、再帰的なネストされたリストと最適化された再帰コールが含まれます。

再帰関数を尾の再帰関数にリファクタリングすることができます。これにより、パフォーマンスの利点が得られます。

再帰を学ぶための良いリソースは、本「The Little Schemer」です。 Q＆A形式を使用して、再帰的に考える方法を教えます。

この投稿は、ジェイコブジャクソンの貢献で更新されました。ジェイコブは、ウェブ開発者、ハイテクライター、フリーランサー、オープンソースの寄稿者です。

以上がJavaScriptによる再帰を理解するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。