27

ウィキペディアの生成再帰の説明は私には明らかですが、構造的再帰の概念については混乱しています。

n 番目のフィボナッチ数を計算する関数と 1 から N までの階乗を計算する関数が構造的か生成的かを説明できますか?

4

1 に答える 1

54

構造的再帰と生成的再帰の主な違いは、再帰プロシージャが処理対象のデータを取得する場所と、そのデータを処理する方法です。具体的には、構造再帰の場合、元の入力データのサブセットに対して再帰呼び出しが行われます。一方、生成再帰の場合、元の入力データから構築/計算されたデータに対して再帰呼び出しが行われます。

たとえば、リンクされたリスト内の要素の数を数えたい場合は、次のようにすることができます。

int NumberOfNodes(ListNode* node) {
    if (node == nullptr) return 0;
    return 1 + NumberOfNodes(node->next);
}

ここでは、 への再帰呼び出しが、すでに存在していた元の入力の一部である に対してNumberOfNodes行われています。node->nextこの場合、再帰は、入力を小さな断片に分割し、小さな断片で再帰することによって機能します。

同様に、BST で値を検索するこのコードは、再帰呼び出しが元の入力のサブパーツに対するものであるため、構造的再帰になります。

TreeNode* Find(TreeNode* root, DataType value) {
    if (root == nullptr) return nullptr;
    if (value < root->value) return Find(root->left, value);
    else return Find(root->right, value);

「構造再帰」という用語は、これらの構造 (リスト、BST など) を再帰的に定義できるという事実に由来しています。

  • リストは何もないか、セルの後にリストが続きます。
  • 二分木は何もないか、2 つの二分木を子として持つノードです。

構造的再帰を行うとき、これらの構造が相互に構築される操作を「元に戻す」ことになります。たとえば、このNumberOfNodes関数は、ノードを取得して既存のリストの先頭に追加するという構成を「元に戻します」。オペレーターはFind、ノードを他の 2 つのツリーに接着する操作を「取り消し」ます。したがって、これらの関数を終了する必要がある理由は簡単にわかります。最終的には、最初にオブジェクトを構築するために行ったすべての操作を「元に戻す」と、再帰が停止します。

一方、次のことを行う Quicksort について考えてみましょう。

  1. ピボットを選択します。
  2. 3 つの新しいリストを作成します。ピボットより小さいすべての要素の 1 つ、ピボットより大きいすべての要素の 1 つ、およびピボットと等しいすべての要素の 1 つです。
  3. これらのリストの 1 番目と 2 番目を再帰的に並べ替えます。
  4. 小さい値、等しい値、大きい値のリストを連結します。

ここでは、元の入力の一部ではなかった小さな配列に対して再帰呼び出しが行われています。リストはデータから作成する必要がありました。(通常、実装はこれらのリストのスペースを再利用しますが、これらのサブリストが入力内に直接存在することは保証されていません)。

自然数になると、この区別はあいまいです。通常、自然数は次のように再帰的に定義されます。

  • 0 は自然数です。
  • nが自然数なら、n+1は自然数です。
  • それ以外は自然数ではありません。

この定義では、数値 n は n + 1 の「一部」です。は構造再帰です:

int Factorial(int n) {
    if (n == 0) return 1;
    return n * Factorial(n - 1);
}

引数 n - 1 は元の入力 n の「一部」であるため、これは構造的再帰です。

同様に、この定義により、n 番目のフィボナッチ数を再帰的に計算すると、構造的再帰としてカウントされます。

int Fibonacci(int n) {
    if (n <= 1) return n;
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

n - 1 は n の一部 (+1 を「元に戻す」ことによって形成される) であり、n - 2 は n - 1 の一部 (+1 を「元に戻す」ことによって形成される) であるため、これは構造的再帰と見なされます。

一方、gcd を計算するこのコードは、構造的再帰ではなく、生成的再帰と見なされます。

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

その理由は、 は と から「a % b計算」されているため、+1 操作をいくつか「元に戻す」ことによって形成されるのではなく、データが生成されるからです。ab

生成再帰が構造的再帰と異なる理由は、それが終了するという保証がないからです。たとえば、次の関数について考えてみます。

int BadTimes(int a, int b) {
    if (a == 0 && b == 0) return 0;
    return BadTimes(a * 2, b - 1);
}

この生成再帰関数は決して終了しません:小さくなり続けてaも大きくなり続けます。b

正直なところ、私はこの区別について聞いたことがなく、個別の数学とプログラミングのコースを教えています。誰かがあなたに違いを知るように要求しない限り、私はそれについてあまり心配しません.

お役に立てれば！

于 2013-01-10T23:05:12.270 に答える