Why output differs if i erase "else" from the function?

Question

I am trying to write a GCD function to calculate gcd of two integers using euclids algorithm. In the function if i erase "else" it outputs 3 which is incorrect . But if i use "else" it outputs 1 which is the correct output. i assume if i don't use "else" the function is still correct. Why am i getting two different outputs.

Here is my 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

Your function has undefined behavior. When the % operator returns a non-zero value, your function is not returning anything at all, so the output is garbage. You need to return the result of the recursive call:

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

However, based on Wikipedia's description of the algorithm, the function should look like this instead:

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

Or, using the other described implementations that don't use recursion at all:

Division-based:

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

Subtraction-based:

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