4

重複の可能性:
再帰関数の例

私は概念としてプログラミングの再帰を研究しようとしてきましたが (私は特に Java を勉強しています)、これが私が最もよく理解していることです:

たとえば、実生活では、再帰とは、2 つのミラーを互いの前に置き、その間に生成されるイメージが再帰的であることです。

しかし、プログラミングでこのアルゴリズムを取得できませんか? 誰かが再帰を理解するための簡単な例を教えてもらえますか?

4

6 に答える 6

19

再帰は、メソッドが計算の一部として自分自身を呼び出すことができるプログラミング手法です (複数のメソッドを使用できる場合もあります。その場合、メソッドは通常、相互に循環的に呼び出します)。

一般的な例は、フィボナッチ数の計算です。

public static long fib(int n) {
    if (n <= 1) return n;
    else return fib(n-1) + fib(n-2);
}

2 つの基本的なコンポーネントは、基本ケース (n<=1例) と再帰ケースです。

再帰アルゴリズムを作成するときは、基本ケースと、再帰ケースを使用して基本ケースに到達する方法を考慮する必要があります (そうしないと、無限再帰になり、スタックが吹き飛ばされます)。

于 2012-11-30T13:50:19.407 に答える
6

基本的に、関数は次の場合に再帰的です。

  1. 関数には単純な基本ケースがあり、
  2. 他のすべてのケースには、基本ケースに帰着するルールがあります。

例として、階乗を計算するには:

public static long factorial(int i)
{
    // This is the base case
    if(i == 0)
    {
         return 1;
    }
    else
    {
        // This reduces the problem to something closer to the base case
        return i * factorial(i - 1);
    }
}
于 2012-11-30T13:54:46.573 に答える
3

一部の計算問題は、問題をより小さな部分問題に分解できるように記述できます。小さいサブ問題は、メインの問題と同じ方法を使用して解決されます。より小さな部分問題がより大きな問題のより小さなケースである場合、それ自体をさらに分解することができます。

最終的に、問題は非常に小さいため、それ以上分解せずに解決できます。これは基本ケースとして知られています。基本ケースのソリューションを使用して、より大きな問題のソリューションを構築できます。

a と b が正の整数であるa bを見つけたいとします。これは a * a (b-1)と同じであることがわかります。つまり、(b-1)は元の問題よりも小さい問題ですが、元の問題と同じ手法で解決する必要があります。a (b-1)を解くと、それが a * a (b-2)であることがわかります。

等々。

最終的には a * a * a * ... * a (bb)になります。そして、bb = 0 と a 0 = 1 であることはわかっています。答えはすでにわかっているので、最後のビットを計算する必要はありません。最終的に、a b = a * a * a * ... * 1.

したがって、2 4 = 2 * 2 3 = 2 * 2 * 2 2 = 2 * 2 * 2 * 2 1 = 2 * 2 * 2 * 2 * 2 0 = 2 * 2 * 2 * 2 * 1 です。

このプログラムを作成するには、最初に基本ケースを処理し、次に再帰を使用して他のすべてを処理します。

   pow(a, b){
       if(b == 0){
          return 1;
       }else{

          return a * pow(a, b - 1);
       }
   }

これは再帰の基本的な考え方にすぎないことに注意してください。フィボナッチ数の問題などのさまざまな回答で見られるこれらの例は、非常に非効率的です。問題を解決するメカニズムの 1 つとして再帰を使用する動的プログラミング手法を使用して、より効率的なプログラムを作成できます。

于 2012-11-30T14:07:03.317 に答える
2

再帰的プログラミングは、メソッドまたは関数が繰り返し自分自身を呼び出す数学的帰納法の考え方に基づく手法です。そのため、次のように階乗関数を実装できます。

int fact(int n) {
    if (n < 2) {
            return 1;
    }

    return n * fact(n-1);
}

再帰が確実に終了するようにするために、既知の単純な入力に対して定義された定数出力がある基本ケースを確実に処理する必要があり、各反復で関数のパラメーターをより単純にする必要があることに注意してください (上記の例では、1 を減らしnます)。

于 2012-11-30T13:57:05.057 に答える
1

非常に単純な「再帰的」コード。

リストの一番上のアイテムを処理します。リストからそれを削除し、コードを呼び出してリストの一番上の項目を処理します。

木の根は一定の長さを持ち、2/3の根ごとに別々の根に分割されます。分割された部分は、2/3ルートごとに別々のルートに分割されます。分割された部分の分割された部分は、毎回分割されます。

于 2012-11-30T13:51:57.167 に答える
1

再帰

メソッドは自分自身を呼び出すことができます。これがrecursionです。メソッドの再帰的な実装は、再帰を使用しない対応する実装よりも理解しやすいコンパクトで洗練されたコードにつながるため、よく使用されます。

再帰的プログラミング手法は、(経験上) 3 つの重要なルールを知っています。

  1. 基本ケース: 再帰には基本ケースがあります。常に最初のステートメントは条件付きで、'return' があります。
  2. SubProblem : 再帰呼び出しは、ベース ケースに収束するように、ある意味で解決するのに小さいサブ問題に対処します。
  3. オーバーラップなし: 再帰呼び出しは、オーバーラップするサブ問題を処理しません。

パフォーマンスの観点から、非再帰的なソリューションは高速であり、通常は必要なメモリが少なくて済みます。(例: 二分探索)
しかし、いくつかのタスクは非常に複雑で、再帰的な解決策のみが (多かれ少なかれ理解可能な) コードにつながります。

再帰的二分探索の例:

public static int binSearch(int[] a, int key) {
   return binSearch0(a, key, 0, a.length - 1);
}

public static int binSearch0(int[] a, int key, int from, int to) {
    if (from > to) return -1;
    // looks strange but (from + to) / 2 can oveflow
    // (java bug which was active more than 10 years)
    int mid = from + (to - from) / 2;
    if (key < a[mid]) 
        return binSearch0(a, key, from, mid - 1);
    else if (key < a[mid]) 
        return binSearch0(a, key, mid + 1, to);
    else return mid;
 }

この例では、3 つのルール (ベース、サブ、非オーバーラップ) がすべて表示されます。
再帰関数には多くの場合、開始関数 (例では「binSearch」) があるわけではありません。「binSearch0」は再帰関数です。

于 2012-11-30T14:37:03.997 に答える