[已解决]递归问题求助

xiaobaizzj

def gcd(x, y):
    if y:
        return gcd(y, x%y)
    else:
        return x
   
print(gcd(4, 6))
请大神指点一下，这个求最大公约数函数太简洁了没有理解

最佳答案

月排行榜 / 总排行榜

Twilight6

2021-5-24 22:42:46

看看注释能不能理解吧~：

1. def gcd(x, y):  
   
2.     # 函数开始 x = 4  y = 6   
   
3.     # 第一次递归 x = 6 y = 4
   
4.     # 第二次递归 x = 4 y = 2
   
5. 
   
6.     if y: # 刚开始 y = 6 条件成立执行if代码块
   
7.     # 第一次递归 y = 4 继续进入 if 代码块
   
8.     # 第二次递归 y = 2 继续进入 if 代码块
   
9.     # 第三次递归 y = 0 条件不成立则进入 else 代码块
   
10. 
    
11.         return gcd(y, x % y)
    
12.     # 进入第一次递归 gcd(6,4%6) 即 gcd(6,4)
    
13.     # 进入第二次递归 gcd(4,6%4) 即 gcd (4,2)
    
14.     # 进入第三次递归 gcd (2,4%2) 即 gcd (2,0)
    
15.     else:
    
16.         return x # 第三次递归返回 x = 2
    
17.    
    
18.     # 然后依次返回 先从第三次递归开始 gcd(2,0)  -> gcd(4,2) -> gcd(6,4) -> gcd(4,6)
    
19. 
    
20. print(gcd(4, 6))

复制代码

跳转到最佳答案楼层

Twilight6

看看注释能不能理解吧~：

1. def gcd(x, y):  
   
2.     # 函数开始 x = 4  y = 6   
   
3.     # 第一次递归 x = 6 y = 4
   
4.     # 第二次递归 x = 4 y = 2
   
5. 
   
6.     if y: # 刚开始 y = 6 条件成立执行if代码块
   
7.     # 第一次递归 y = 4 继续进入 if 代码块
   
8.     # 第二次递归 y = 2 继续进入 if 代码块
   
9.     # 第三次递归 y = 0 条件不成立则进入 else 代码块
   
10. 
    
11.         return gcd(y, x % y)
    
12.     # 进入第一次递归 gcd(6,4%6) 即 gcd(6,4)
    
13.     # 进入第二次递归 gcd(4,6%4) 即 gcd (4,2)
    
14.     # 进入第三次递归 gcd (2,4%2) 即 gcd (2,0)
    
15.     else:
    
16.         return x # 第三次递归返回 x = 2
    
17.    
    
18.     # 然后依次返回 先从第三次递归开始 gcd(2,0)  -> gcd(4,2) -> gcd(6,4) -> gcd(4,6)
    
19. 
    
20. print(gcd(4, 6))

复制代码