Warum unterscheidet sich die Ausgabe, wenn ich "else" von der Funktion lösche?

Question

Ich versuche, eine GCD-Funktion zu schreiben, um gcd zweier ganzer Zahlen mit dem euclids-Algorithmus zu berechnen. Wenn ich in der Funktion "else" lösche, gibt es 3 aus, was falsch ist. Aber wenn ich "else" verwende, gibt es 1 aus, was die korrekte Ausgabe ist. Ich nehme an, wenn ich "else" nicht verwende, ist die Funktion noch richtig. Warum bekomme ich zwei verschiedene Ausgänge.

Hier ist mein Code,

#include <iostream> 

using namespace std; 


int euclidGcd(int x , int y){ 

    if(x%y!=0) 
     euclidGcd(y , x%y); 
    else 
     return y; 

} 

int main(){ 

    cout<<euclidGcd(2,3)<<"\n"; 


    return 0; 
} 

Answer 1

Ihre Funktion hat undefiniertes Verhalten. Wenn der Operator % einen Wert ungleich null zurückgibt, gibt Ihre Funktion überhaupt nichts zurück, so dass die Ausgabe unbrauchbar ist. Sie müssen das Ergebnis des rekursiven Aufrufs zurückzukehren:

int euclidGcd(int x, int y) 
{ 
    if ((x % y) != 0) 
     return euclidGcd(y, x % y); // <-- here 
    else 
     return y; 
} 

jedoch

, basierend auf Wikipedia's description des Algorithmus, sollte die Funktion wie diese stattdessen aussehen:

int euclidGcd(int x, int y) 
{ 
    if (y != 0) 
     return euclidGcd(y, x % y); 
    else 
     return x; 
} 

Oder die anderen beschriebenen Implementierungen verwenden, verwenden Sie keine Rekursion überhaupt:

Abteilung Basis:

int euclidGcd(int x, int y) 
{ 
    while (y != 0) 
    { 
     int t = y; 
     y = x % y; 
     x = t; 
    } 
    return x; 
} 

Subtraktionsbasiert:

int euclidGcd(int x, int y) 
{ 
    while (x != y) 
    { 
     if (x > y) 
      x -= y; 
     else 
      y -= x; 
    } 
    return x; 
}