[解決済み] 構造的再帰と生成的再帰はどのように違うのですか？

質問

の生成再帰の記述は ウィキペディア はわかるのですが、構造的再帰の概念がよくわかりません。

フィボナッチ数nを計算する関数と1からNまでの階乗を計算する関数のどちらが構造的なのか生成的なのか、誰か説明してください。

どのように解決するのですか？

構造的再帰と生成的再帰の重要な違いは、再帰手続きが動作するデータをどこで取得し、そのデータをどのように処理するかという点である。具体的には、構造的再帰では、元の入力データのサブセットに対して再帰的な呼び出しが行われる。一方、生成的再帰では、元の入力データから構築/計算されたデータに対して再帰的な呼び出しが行われる。

例えば、リンクリストの要素数を数える場合、次のようになります。

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分木は、何もないか、2つの2分木を子として持つノードのどちらかです。

構造的再帰を行う場合、これらの構造が互いに構築された操作を元に戻すことになります。 例えば NumberOfNodes 関数は、ノードを取って既存のリストに前置する構造を元に戻します。 また Find 演算子 "undoes" ノードを他の2つの木に接着させる操作です。 したがって、これらの関数が終了しなければならない理由は簡単です。最終的には、最初にオブジェクトを構築するために行ったすべての操作を"undo"し、再帰を停止するのです。

一方、クイックソートを考えてみると、次のようなことができる。

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

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

この区別は、自然数に関しては曖昧です。 通常、自然数は次のように再帰的に定義されます。

• 0は自然数である。
• nを自然数とすると、n＋1は自然数である。
• それ以外のものは自然数ではありません。

この定義のもとでは、数nはn + 1の"part"である。 したがって、このn！を計算する再帰的コードは構造的再帰である。

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

これは構造的再帰であり、引数n - 1は元の入力nの"part"であったからである。

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

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

n - 1 は n の一部（"undo" +1によって形成）であり、n - 2 は n - 1 の一部（"undo" +1によって形成）なので、これは構造再帰と見なされます。

一方、このgcdを計算するコードは、構造的再帰ではなく、生成的再帰と考えられるだろう。

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

その理由は a % b から計算されます。 a と b というように、いくつかの+1操作を取り消すことでデータが生成されます。

生成再帰が構造再帰と異なる理由は、終了する保証がないことである。 例えば、このような関数を考えてみよう。

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

この生成再帰的な関数は決して終了しない。 a は大きくなり続けるが b は小さくなり続けている。

正直、この区別は初めて聞きました。私は離散数学とプログラミングのコースを教えています。 この違いを知ることを要求する人がいない限り、あまり気にすることはないでしょう。

お役に立てれば幸いです。