017/022课求最大公约数的答案没看懂

changhaitian

1、22课 递归
def gcd(x,y):
   if y:
       return gcd(y,x%y)   -------请问这里不是返回（x,y）的形式吗？为什么会是取最大公约数呢？
   else:
       return x

print(gcd(113,6))
2、17课 乐高积木
def gcd(x, y):
    while y:
        t = x % y         （t是x除以y的余数看懂了，后面为什么x = y,y =t呢？）
        x = y
        y = t

    return x
   
print(gcd(4, 6))

请问两种求值方法有啥异同点，能够详细解释下取值的过程吗？

谢家进

递归的思想对我们这种初学者来说真是 有点点难，我认为重点在于找到可递归的规律吧。
满足递归有两条件，一是函数自身调用自己，二是有能够结束的条件。

你可以先搞懂第二种，再来看第一种应该就不会那么乱了。
你说x=y,y=t不明白，那些有编程经验的人一看，应该就知道这不过是两个值交换的一惯做法。
像我们这种初学者就要一步一步走过程，比如说先调用方法
gcd(4,6),传入的值，x等于4，y等于6
while y: (这时y是6，非0为True，进入循环)
t= x%y  ( t等于4%6，也就t等于4)
x = y  (x等于6)
y = t   (y等于4)

while y: (这时y是4，进入循环)
t= x%y  ( t等于6%4，也就t等于2)
x = y  (x等于4)
y = t   (y等于2)

while y: (这时y是2，进入循环)
t= x%y  ( t等于4%2，也就t等于0)
x = y  (x等于2)
y = t   (y等于0)

while y: (这时y是0，退出循环)
t= x%y    (x等于2，这里不会执行了)
x = y
y = t

return x; （这时x等于2）



至于递归那里 你说返回 (x,y )形式，也不是不可以，可以改成像2那样
def gcd(x,y):
   if y:
       t = x % y
       x = y
       y = t
       return gcd(x,y)  
   else:
       return x

既然能够简化程序，何必写那么多行是吧。

changhaitian

谢家进 发表于 2016-10-20 10:18
递归的思想对我们这种初学者来说真是 有点点难，我认为重点在于找到可递归的规律吧。
满足递归有两条件， ...

谢谢你的细心解答，根据你的解答，我把思路重新整理了一遍。
作为初学者，我觉得搞清楚基本的概念非常重要，比如说迭代的概念，函数的赋值方法。
其实递归也是循环的一种，不过更强调的是对函数本身的调用？
第十七课 方法一，求最大公约数：
def gcd(x,y):
    while y:（在y循环中）
        t = x%y (t是x除以y的余数)
        x = y (把y的值赋予x)
        y = t (把余数t的值赋予y)
当 x = 4, y = 6时：
    进入y循环，
        t = x%y = 4
        x = y = 6
        y = t = 4
    再进入y循环,现在x = 6,y = 4:
        t = x%y = 2
        x = y = 4
        y = t = 2
     又再次进入y循环，x = 4 ,y =2
        t = x%y = 0
        x = y = 2
        y = t = 0
     因为 y = 0 为 false,循环终止
      
       return x (取第三次循环y 的值2)
      
       所以，（x,y）的最大公约数为 2
第十九课 方法二： 递归的思想
递归满足两个条件： 1、函数自己调用自己。2有正确的结束的条件。
def gcd(x,y):
       if y:(如果y != 0)
           return gcd (y,x%y)  返回，让 x = y,且 y = x%y (y取值x%y的余数)
          相当于， t = x%y,x = y, y =t
      else:(如果 y ==0)
           return x (返回最后一次阶乘中ｘ的值，ｘ就是原两数的最大公约数）

wushuang123

醍醐灌顶啊

dh89

学习了

飘渺463431810

瞬间明白了，谢谢

Ramsey

涨知识了

王先壮

谢家进 发表于 2016-10-20 10:18
递归的思想对我们这种初学者来说真是 有点点难，我认为重点在于找到可递归的规律吧。
满足递归有两条件， ...

牛逼答主，，，为你点赞！！

王先壮

醍醐灌顶啊

nwyh

想问下 为什么要设成return x

还是鱼头好

changhaitian 发表于 2016-10-20 20:34
谢谢你的细心解答，根据你的解答，我把思路重新整理了一遍。
作为初学者，我觉得搞清楚基本的概念非常 ...

艰难理解中……以及顺道为22课答案解答马一下QAQ

终于艰难地再次看到22课
大致理解了22课这一题的思路

KONGYIYAO

mark,终于懂了！