データ構造の再帰：どのように機能するか、タイプと使用時期

データ構造における再帰の定義から始めましょう。 後で、さまざまなタイプの再帰と、さまざまな問題を解決するために再帰がどのように使用されるかについて説明します。

再帰とは何ですか？

簡単に言えば、再帰は問題解決であり、場合によっては、非常に特別で排他的な特性を持つプログラミング手法です。 再帰では、関数またはメソッドは、問題を解決するためにそれ自体を呼び出す機能を持っています。 再帰のプロセスには、問題をそれ自体のより小さな種類に変えることによって問題を解決することが含まれます。

関数がそれ自体を呼び出すプロセスは、直接的にも間接的にも発生する可能性があります。 この呼び出しの違いにより、さまざまなタイプの再帰が発生します。これについては、後で説明します。 再帰を使用して解決できる問題には、グラフのDFS、ハノイの塔、さまざまな種類のツリートラバーサルなどがあります。 再帰やその他のデータサイエンスの概念については、IIIT-Bのデータサイエンスオンラインコースをご覧ください。

読む： 13の興味深いデータ構造プロジェクトのアイデア

再帰はどのように機能しますか？

再帰の概念は、問題が1つ以下のバージョンで表される場合、問題をはるかに簡単に、より短時間で解決できるという考えに基づいて確立されています。 再帰を停止するための基本条件を追加することは、このアルゴリズムを使用して問題を解決するためのもう1つの重要な部分です。

人々はしばしば、それ自体の観点からエンティティを定義することは不可能であると信じています。 再帰はその理論が間違っていることを証明します。 そして、この手法が正しい方法で実行されれば、非常に強力な結果が得られる可能性があります。 いくつかの例を使用して、再帰がどのように機能するかを見てみましょう。 文とは何ですか？ 接続詞を使用して結合された2つ以上の文として定義できます。 同様に、フォルダは、ファイルやフォルダを保存するために使用されるストレージデバイスである可能性があります。 祖先は、家系図の1つの親であり、別の家族の祖先である可能性があります。

再帰は、いくつかの非常に単純な単語を使用して複雑な状況を定義するのに役立ちます。 通常、祖先をどのように定義しますか？ 親、祖父母、または曽祖父母。 これは続く可能性があります。 同様に、フォルダの定義は難しい作業になる可能性があります。 それは、それ自体がファイルとフォルダーである可能性があるいくつかのファイルとフォルダーを保持するものである可能性があり、これは再び続く可能性があります。 これが、再帰によって状況の定義が通常よりもはるかに簡単になる理由です。

再帰も十分なプログラミング手法です。 再帰サブルーチンは、直接または間接的に自分自身を呼び出すサブルーチンとして定義されます。 サブルーチンを呼び出すことは、サブルーチンの定義に、定義されたサブルーチンを呼び出すというcallステートメントがすでに含まれていることを直接意味します。

一方、サブルーチンの間接呼び出しは、サブルーチンが別のサブルーチンを呼び出し、次に元のサブルーチンを呼び出すときに発生します。 再帰では、数行のコードを使用して、非常に複雑なタスクを記述することができます。 ここで、すでに触れたさまざまなタイプの再帰に注意を向けましょう。

また読む：学ぶべきトップ6プログラミング言語

再帰の種類

すでに述べたように、再帰には2つのタイプしかありません。 それらが互いにどのように異なるかを見てみましょう。 直接再帰は、元の関数、メソッド、またはサブルーチンを呼び出す1つのステップのみを含むため、より簡単な方法です。 一方、間接再帰にはいくつかのステップが含まれます。

最初の呼び出しは、元のメソッドによって2番目のメソッドに対して行われ、2番目のメソッドは元のメソッドを呼び出します。 この一連の呼び出しは、いくつかのメソッドまたは関数を特徴とすることができます。 簡単に言えば、間接再帰の深さには常に変化があり、この深さの変化はプロセスに含まれるメソッドの数に依存すると言えます。

直接再帰を使用して、1つの関数を単独で呼び出すことができます。 一方、間接再帰を使用すると、他の関数を使用して複数のメソッドまたは関数を呼び出すことができ、それも何度も呼び出すことができます。 間接再帰はオーバーヘッドを発生させませんが、直接再帰はオーバーヘッドを発生させます。

再帰はいつ使用されますか？

再帰または反復を使用できる状況があります。 ただし、問題に対してより自然に適合すると思われる解決策を常に選択する必要があります。 データの抽象化に関しては、再帰が常に適切なオプションです。 多くの場合、再帰的定義を使用してデータと関連する操作を定義します。

また、データに対するさまざまな操作の実装に関連する問題のほとんどの場合、再帰が自然な解決策であると言っても間違いありません。 ただし、再帰に関連する特定の事項があり、すべての問題に対して最善の解決策とはならない場合があります。 このような状況では、反復法のような代替方法が最適です。

再帰の実装は多くのスタックスペースを使用するため、冗長性が生じることがよくあります。 再帰を使用するたびに、メソッドを呼び出して、そのメソッドの新しいインスタンスを作成します。 この新しいインスタンスは、スタックに格納され、戻り時に取得されるさまざまなパラメーターと変数を運びます。 したがって、再帰は他のソリューションよりも単純なソリューションですが、通常は最も実用的ではありません。

また、さまざまな問題の反復または再帰を選択するのに役立つ事前定義されたルールのセットはありません。 再帰を使用する最大の利点は、それが簡潔な方法であるということです。 これにより、通常よりも読みやすく、メンテナンスも簡単になります。 しかし、再帰的メソッドは、多くのストレージスペースを必要とし、実装中に多くの時間を消費するため、私たちが利用できる最も効率的なメソッドではありません。

いくつかのことを覚えておくと、問題の再帰を選択することが正しい方法であるかどうかを判断するのに役立ちます。 解決しようとしている問題が再帰的な用語で言及されており、再帰的な解決策がそれほど複雑ではないと思われる場合は、再帰を選択する必要があります。

ほとんどの場合、再帰によって、使用するアルゴリズムの実装が単純化されることを知っておく必要があります。 ここで、反復と再帰の使用に関連する複雑さが特定の問題で同じである場合、より効率的である可能性が高いため、反復を使用する必要があります。

また、チェックしてください：仕事を得るための23の最高のコンピュータプログラミングコース

結論

ただし、決定を下すのがそれほど簡単ではない場合もあります。 効率とシンプルさのどちらかを選択する必要があります。 経験豊富な設計者であれば、効率を重視する時期と、それよりも単純さや簡潔さを選択する時期を正確に理解できます。

データ構造、データサイエンスについて知りたい場合は、IIIT-BとupGradのデータサイエンスのエグゼクティブPGプログラムをご覧ください。これは、働く専門家向けに作成され、10以上のケーススタディとプロジェクト、実践的なハンズオンワークショップ、業界とのメンターシップを提供します。専門家、業界のメンターと1対1で、400時間以上の学習とトップ企業との仕事の支援。