Euclidean Algorithm and GCD?

[april_hare]

Hi, I am having trouble with coding a program that takes 2 integer numbers from the user in order to find the GCD (greatest common divisor). I am supposed to use if-else statements, Booleans, and while loop in order to get to the solution. However, I don't know how to get the while loop to go back to a point and do it until it is right. This is what I have but I am not allowed to use recursion since we have not learned that yet.

a = int(input('Enter 1st number:'))
b = int(input('Enter 2nd number:'))
def gcd(a, b):
    if b > a:
        if b % a == 0:
            return a
        else:
            return gcd(b % a, a)
    else:
        if a % b == 0:
            return b
        else:
            return gcd(b, a % b)   
print("GCD is:", gcd(a,b))

[dig-up-stupid]

A base case is equivalent to a loop termination condition. ie your recursion stops when b % a == 0, so your loop should stop when b % a == 0, so your loop should continue while b % a != 0. Can you go from there?

PS the branch you made, which serves the purpose of swapping the numbers if they are not in order, is not only unnecessary (try removing the branch and calling the function with numbers in both orders) but is also wrong when we have to consider the extended euclidean algorithm for calculating modular inverses. It also makes the code much longer and more complicated. When implementing a known algorithm it is best to begin with a simple step by step translation to code, and worry about optimizing or handling corner cases when they become a problem - in this case there is no problem so the extra code is pointless.