再帰


難易度 簡単に
よく聞かれる Amazon (アマゾン) インフォシス MAQ
再帰 スタック 理論

再帰とは何ですか?

再帰は、それ自体を呼び出す関数として単純に定義されます。 以前に解決したサブ問題を使用して、より大きな問題を計算します。

これはプログラミングで最も重要でトリッキーな概念のXNUMXつですが、再帰をいくつかの実際の例と関連付けようとすると、簡単に理解できます。

鏡の前に鏡を置いたときの状況を考えてみてください。

再帰

これは、ミラーがミラーを反射している、ミラーを反射している、などの理由で発生します。

これはまさに再帰が行うことです。

それでは、再帰がどのように機能するかを視覚化してみましょう。

すべてのエッジに三角形を描画する関数を定義するとします。 結果の図を想像できますか?再帰

上記の両方の例で、終わりのないサブ問題が見られました(ミラーは互いに反射し続け、ミラーの数は無限にあるように見えます。XNUMX番目の例では、図は無限に大きくなり続けます)。

これにより、この無限構造を回避するすべての再帰関数に終了条件を設定する必要があることがわかります。 この状態はとして知られています 規範事例。

再帰を形成する手順

  1. 規範事例
  2. 小さな問題の再帰的な呼び出し
  3. 解決されたサブ問題を使用したより大きな問題の計算

例を挙げて理解してみましょう。

質問:1から始まるn個の連続する自然数の合計を計算します。

int sum(int n){

    // Base Case

    if(n==1){

        return n;

    }

    else{

        int smallerSum=sum(n-1);      //recursive call for smaller problem

        return n+smallerSum;         // solve bigger problem using solved smaller sub-problems

    }

}

再帰とスタック

function と呼ばれ、メモリを占有します スタック 関数の実行に関する詳細を保存します。 また、関数が終了すると、関数が占有していたメモリも解放されます。 私たちが知っているように、今は再帰的に、関数はそれ自体で呼び出されます。 したがって、すべての関数呼び出しで、現在実行中の関数の情報を保持するために、メモリのブロックがスタックに作成されます。 関数が終了すると、外部関数に記述された呼び出しステートメントに戻ります。つまり、外部関数は停止した場所から再開されます。 上記のn = 3の例のメモリ構造を見てみましょう。

再帰とスタックの関連付けを念頭に置くと、ベースケースがない場合、プログラムがスタックオーバーフローに悩まされ、制限時間を超えてしまうことは容易に理解できます。

直接再帰と間接再帰の違い

直接再帰

  1. 同じ関数がそれ自体を呼び出すとき、それはとして知られています 直接再帰.
  2. 直接再帰では、呼び出し元と呼び出された関数の両方が同じです。
  3. ワンステップの再帰呼び出しがあります。

直接再帰関数のコード構造:

return_type func_name(arguments)
{
  // some code...

  func_name(parameters);

  // some code...
}

間接再帰

  1. 関数が、その親関数を直接または間接的に呼び出している別の関数を呼び出す場合、それは次のように知られています。 間接再帰。
  2. 間接再帰では、呼び出し関数と呼び出された関数が異なります。
  3. マルチステップの再帰呼び出しがあります。

間接再帰関数のコード構造:

return_type func_name1(arguments)
{
  // some code...

  func_name2(parameters);

  // some code...
}

return_type func_name2(arguments)
{
  // some code...

  func_name1(parameters);

  // some code...
}

再帰の種類

  1. テーラード再帰
    • 関数の最後に実行されたステートメントが再帰呼び出しである場合。
    • 最後の再帰呼び出しのみをスタックに保持することができます。
    • 例:
int sum(int n,int &ans){
    if(n==0){
        return ans;
    }
    else{
        ans=ans+n;
        return sum(n-1,ans);     // last statement to be executed is recursive call

    }
}
  1. 尾なし再帰
    • 再帰呼び出しステートメントの後に実行するステートメントが関数に残っている場合。
    • 再帰呼び出しは、評価が終了するまでスタックに残ります。
    • 例:
int sum(int n){
    if(n==1){
        return n;
    }
    else{
        int smallerSum=sum(n-1);      //recursive call for smaller problem
        return n+smallerSum;         //statements to be executed after recursive call
    }
}

反復で再帰を使用する場合

どちらのアプローチにもそれぞれ長所と短所があるため、特定の問題を解決するためにどちらを使用する必要があるかを理解する必要があります。

再帰は、次の問題を解決するためのより直感的なアプローチです。 分割統治 マージソートのように、問題を再帰的にサブ問題に分割し続けることができます。これは、たとえば、反復アプローチを使用して実行するのが難しい場合があります。 ツリートラバーサル(注文、事前注文、事後注文)。 ただし、複数の関数呼び出しのオーバーヘッドがないため、反復アプローチの方が再帰よりも高速であることも事実です。

注:問題を解決するには、反復または再帰、あるいはその両方を使用できます。

再帰は明示的な呼び出しスタックを使用した反復に置き換えることができ、反復はtail_recursionに置き換えることができます。 私たちプログラマーは、メモリを使用したコードの簡単でクリーンな記述と時間の最適化のバランスをとる必要があります。

別の質問を解決してみましょう:

nの階乗を計算します。

C ++の実装

#include <iostream>
using namespace std;
int fact(int n){
   // Base Case
   if (n <= 1)
        return 1;
   else 
       return n*fact(n-1);    
}
int main(){
   int n=5;
   cout<<fact(n);
   return 0;
}
Output: 15

Java実装

class Main{  
 static int fact(int n){    
  if (n<=1)    
    return 1;    
  else    
    return(n * fact(n-1));    
 }    
 public static void main(String args[]){  
  int n=5;   
  System.out.println(fact(n));    
 }  
}
Output: 15

読んでくれてありがとう!!

しばらくお待ちください。他のブログもチェックしてください。 訂正/提案がある場合はコメントしてください。

リファレンス