欧几里德算法在递归函数中的应用问题

Question

我是一个初学者，已经在Pythonutor上学习了一段时间了，我在27个步骤中得到了“final”的正确值，但似乎不知道如何让while循环停止执行和计算余数。如何从if循环中获取返回值以成为程序的最终输出？在这个例子中，我们使用欧几里德算法进行计算

def gcdRecur(a, b):
    '''
    a, b: positive integers
    
    returns: a positive integer, the greatest common divisor of a & b.
    '''
final=''    
high=max(a,b)
    result=min(a,b)
    while high%result>0:
        result-=1
        return result*gcdRecur(b,(a%b))
    if high%result==0:
        final=result
        return final
a=1071 
b=462
final_ans=gcdRecur(a,b)
print(final_ans)
        

Answer 1

我想你已经从欧几里得的角度来考虑了。如果您坚持输入为正整数（即既不是0也不是负），则可以使用欧几里得的基于减法的算法：

def gcdRecur(a, b):
    '''
    a, b: positive integers
    returns: a positive integer, the greatest common divisor of a & b.
    '''

    if a == b:
        return a

    if a > b:
        a -= b
    else:
        b -= a

    return gcdRecur(a, b)

并避免min()、max()和模（%）。如果使用欧几里德算法的模变量，则不需要对输入值进行严格约束，可以递归表示为：

def gcdRecur(a, b):
    return a if not b else gcdRecur(b, a % b)