如何用递归法去利用欧几里得算法求最大公约数？

Valorie

第22节课后题最后一个：

def gcd(x, y):
    if y:
        return gcd(y, x%y)
    else:
        return x
   
print(gcd(4, 6))

请问大家，这个答案的return gcd(y  ,x%y)
具体是怎样运算的？

Twilight6

def gcd(x, y):  #初始x=4，y=6 ；第一次递归x=6,y=4 ；第二次递归x=4，y=2；第三 x=2，y=0
    if y:       # y=6 条件成立； y=4条件成立  ；y=2条件成立   ； y=0条件不成立
        return gcd(y, x % y) # 开始递归x=6，y=4;开始第二次递归x=4，y=2；开始第三次递归x=2，y=0
    else:
        return x  # 最终递归返回 x = 2
print(gcd(4, 6))

---

如果帮助到你了，记得设置最佳~

Twilight6

Twilight6 发表于 2020-5-18 22:20

---

如果帮助到你了，记得设置最佳~

一个分号算一次递归哈，你要分开看