Greatest Common Divisor, Recursive code

Hello,

This code uses recursion to find the GCD of two numbers that are inputed. The code works but for some reason GCD is being assigned to 0 at the end. The test case I am using sets greatestCommonDivisor(10007,500).

Any help is greatly appreciated

The code is as follows:

function GCD = greatestCommonDivisor(a, b)
if(a > b)
    temp1 = a;
    temp2 = b;
else    
    temp1 = b;
    temp2 = a;
end

if temp1 == 0
    GCD = temp2;
    return
elseif temp2 == 0
    GCD = temp1;
    return
else    
    r = rem(temp1, temp2);
end


if(r == 0)
    disp(temp2)
    if(temp2 == 1)
        GCD = 1;
        disp(GCD)
        return
    else    
        GCD = temp2;
        return
    end
else
    greatestCommonDivisor(temp2, r);
end
end

[Jalaj Gambhir]

Hi,

I do not see where GCD is assigned to 0, can you provide more clarifications/ output screenshot or something? Works fine for me, with GCD = 1 at the end.

Answer 1

[Deepak]

Hi @Kitt Naughton, To my understanding, you have written code to calculate GCD of two integers.

Your code works fine, but the GCD variable is being assigned to 0 at the end.

To resolve this issue, when calling the recursive method “greatestCommonDivisor(temp2, r)” at the end, you need to assign the return value to the output variable GCD.

GCD = greatestCommonDivisor(temp2, r); 

It is important to assign the result of a recursive call to a variable so that the result can be returned up the call stack.

By assigning “GCD = greatestCommonDivisor(b, r)” you capture this result and ensure it is returned correctly.

Here is the updated MATLAB code:

function GCD = greatestCommonDivisor(a, b) 
    if(a > b) 
        temp1 = a; 
        temp2 = b; 
    else     
        temp1 = b; 
        temp2 = a; 
    end   

    if temp1 == 0 
       GCD = temp2; 
       return 
    elseif temp2 == 0 
        GCD = temp1; 
        return 
    else     
        r = rem(temp1, temp2); 
    end 

    if(r == 0) 
        disp(temp2) 
        if(temp2 == 1) 
            GCD = 1; 
            disp(GCD) 
            return 
        else     
            GCD = temp2; 
            return 
        end 
    else 
        GCD = greatestCommonDivisor(temp2, r); 
        disp(GCD); 
    end 
end 

I hope this helps.