0

gcd は再帰関数でなければなりません。void を返す必要があります。2 つの正の整数を取り、GCD を 3 番目のパラメーターに配置する必要があります。

これが私のコード化された gcd 関数です。しかし、再帰関数ではないことに気付きました。このコードを再帰関数に変更するにはどうすればよいですか?

void gcd(int *x, int *y) {
int i;
getValuesForGCD(x, y);
for (i = *x; i >= 1; i--)
{
    if (*x % i == 0 && *y % i == 0)
    {
        printf("The GCD of %d and %d is %d", *x, *y, i); 
        break;
    }
}
}
4

3 に答える 3

6

GCD は自然に再帰式として定義されます。これは単純に再帰関数に変換されます。

gcd(a, 0) = a
gcd(a, b) = gcd(b, a % b)

これをCフォーマットで書いて、それだけです。

于 2013-02-15T15:07:31.163 に答える
2 
int gcd(int a, int b) { 
   if (b == 0) 
   then return a
   else return gcd(b, a % b);
}

a と b は負でない数でなければならないことに注意してください。

良いことに、これは末尾再帰であるため、非再帰メソッドと同じくらい高速に実行されます。

于 2013-02-15T15:13:09.820 に答える
1

通常、人々は再帰を導入するのではなく、削除するように働きます。

反復アルゴリズムを再帰アルゴリズムにリテラル変換したい場合は、次のようになります。

void gcdrecursive(int *x, int *y, int i)
{
    if (i >= 1) {
        if (*x % i == 0 && *y % i == 0) {
            printf("The GCD of %d and %d is %d", *x, *y, i); 
        } else {
            gcdrecursive(x, y, i - 1);
        }
    }
}

void gcd(int *x, int *y) {
    getValuesForGCD(x, y);
    gcdrecursive(x, y, *x);
}

反復ソリューションを再帰に変換するには、各ループを再帰関数に変換します。この関数は、ループの 1 つの反復を実行し、次の反復のためにそれ自体を再帰的に呼び出します。ループを中断することは、再帰を停止することに対応します。あなたの例では、ループは2つの理由で中断します.GCDが見つかるか、iゼロに達します。

これは gcd に最適なアルゴリズムではありませんが、提供された関数を受け取り、要求に応じて再帰的に変換することに注意してください。

于 2013-02-15T15:23:37.313 に答える