[已解决]关于第十七讲函数，求最大公约数问题的返回值问题

xkcx1988

作业要求是编写一个函数，利用欧几里得算法求最大公约数

1. 
   
2. >>> def gcd(a,b):
   
3.         if a<b:
   
4.                 a,b=b,a
   
5.         k=a%b
   
6.         if k==0:
   
7.                 print(b)
   
8.                 return b
   
9.         else:
   
10.                 gcd(b,k)
    
11. 
    
12. >>> gcd(12,4)
    
13. 4
    
14. 4
    
15. >>> gcd(3,1)
    
16. 1
    
17. 1
    
18. >>> gcd(5,3)
    
19. 1
    
20. >>>
    

复制代码

这是我编写的求最大公约数的函数，可是有一个问题，为什么当求5和3的最大公约数时，只能通过print(b)这个语句打印初1，而return b 这个语句就不起作用了，其他时候，return b的语句都会有作用。谢谢各位大神帮忙看看。

最佳答案

月排行榜 / 总排行榜

和vvv

2017-7-24 16:19:16

因为前面两个gcd(12,4)和gcd(3,1)都没有递归调用，直节在这一步结束程序：

1. if k==0:
   
2.                 print(b)
   
3.                 return b

复制代码

所以会有返回值。而gcd(5,3)第一次k = 5 % 3 = 2,不为零，因此递归调用gcd(3,2)，一直调用，直到k=0。这是返回值b=1。但是递归调用并没有结束，还有一个回溯过程。现将这个返回值传到上一层，一直到最后。所以最后的返回值在else下的函数中，因此，这样可以保证能够有返回值：

1. def gcd(a, b):
   
2.     if a < b:
   
3.         a, b = b, a
   
4.     k = a % b
   
5.     if k == 0:
   
6.         print(b)
   
7.         return b
   
8.     else:
   
9.         w = gcd(b, k)
   
10.         return w
    
11. 
    
12. 
    
13. f = gcd(5, 3)
    
14. print(f)

复制代码

而如果还是你那种写法，遇到递归调用的情况，最终的返回值保存在这里：

1. else:
   
2.                 gcd(b,k)

复制代码

但并没有return语句，因此会返回空，也就是None。这就是为什么gcd(5,3)没有打印出返回值的原因。

跳转到最佳答案楼层

和vvv

因为前面两个gcd(12,4)和gcd(3,1)都没有递归调用，直节在这一步结束程序：

1. if k==0:
   
2.                 print(b)
   
3.                 return b

复制代码

所以会有返回值。而gcd(5,3)第一次k = 5 % 3 = 2,不为零，因此递归调用gcd(3,2)，一直调用，直到k=0。这是返回值b=1。但是递归调用并没有结束，还有一个回溯过程。现将这个返回值传到上一层，一直到最后。所以最后的返回值在else下的函数中，因此，这样可以保证能够有返回值：

1. def gcd(a, b):
   
2.     if a < b:
   
3.         a, b = b, a
   
4.     k = a % b
   
5.     if k == 0:
   
6.         print(b)
   
7.         return b
   
8.     else:
   
9.         w = gcd(b, k)
   
10.         return w
    
11. 
    
12. 
    
13. f = gcd(5, 3)
    
14. print(f)

复制代码

而如果还是你那种写法，遇到递归调用的情况，最终的返回值保存在这里：

1. else:
   
2.                 gcd(b,k)

复制代码

但并没有return语句，因此会返回空，也就是None。这就是为什么gcd(5,3)没有打印出返回值的原因。

xkcx1988

和vvv 发表于 2017-7-24 16:19
因为前面两个gcd(12,4)和gcd(3,1)都没有递归调用，直节在这一步结束程序：

所以会有返回值。而gcd(5,3) ...

谢谢你，厉害厉害