[已解决]递归的这段代码怎么理解呢~~~

xinyishuihan

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

这段用递归，用欧几里得算法求最大公约数怎么理解啊

最佳答案

月排行榜 / 总排行榜

stone1

2017-5-23 20:45:10

这种方法主要是采用辗转相除法来求最大公约数  例如
1: gcd（12,8）代入递归方程
2: y=8>0 ，再调用函数gcd（8,12%8）=gcd(8,4)
3: 进入第二层递归，此y=4>0，再调用gcd(4,8%4)=gcd(4,0)
4: 进入递归，此时y=0,直接返回x=4 就是最大公约数了

对于一般的函数求解，可以采用试数的方式来理解程序执行的过程，如果是要这个方法的证明可以在网上搜一些资料

跳转到最佳答案楼层

Lis

对任意非零的y，先执行gcd(x, y),若y<x,那么x%y == x,这样就保证gcd(x, y)中，x比y大。然后再依靠欧几里算法求得最大公约数

stone1

这种方法主要是采用辗转相除法来求最大公约数  例如
1: gcd（12,8）代入递归方程
2: y=8>0 ，再调用函数gcd（8,12%8）=gcd(8,4)
3: 进入第二层递归，此y=4>0，再调用gcd(4,8%4)=gcd(4,0)
4: 进入递归，此时y=0,直接返回x=4 就是最大公约数了

对于一般的函数求解，可以采用试数的方式来理解程序执行的过程，如果是要这个方法的证明可以在网上搜一些资料

7728821314502

def gcd(x, y):
    if y:
        return gcd(y, x%y)
    else:
        return x
   
print(gcd(2, 4))
过程是这样的


if 4:
  return gcd(4,2)

if 2:
  return gcd(2,0)

if 0:
  return 2


去网上查一下【欧几里得算法】是怎样的 就懂了

yongxi

同样的问题，天天都能遇到。这个问题我在论坛至少回答了3次以上。 请楼主提问前先搜索下论坛！