[已解决]关于第22讲，

hero533

小甲鱼给的是欧几里得算法，
但是我用的是辗转相减法，请大佬帮我看看有没问题

1. def fun1(a,b):
   
2.     if a == b:
   
3.         return a
   
4.     else:
   
5.         if a > b:
   
6.             return fun1(a-b,b)
   
7.         else:
   
8.             return fun1(a,b-a)
   
9. print(fun1(5, 10))  

复制代码

         嘿嘿

最佳答案

月排行榜 / 总排行榜

逃兵

2020-11-24 11:20:31

有两个问题
1.运算时间非常的长
2.在运算数值较大时会超出了最大递归深度

1. >>> def fun1(a,b):
   
2.     if a == b:
   
3.         return a
   
4.     else:
   
5.         if a > b:
   
6.             return fun1(a-b,b)
   
7.         else:
   
8.             return fun1(a,b-a)
   
9. 
   
10.         
    
11. >>> fun1(9999,3)
    
12. Traceback (most recent call last):
    
13.   File "<pyshell#27>", line 1, in <module>
    
14.     fun1(9999,3)
    
15.   File "<pyshell#26>", line 6, in fun1
    
16.     return fun1(a-b,b)
    
17.   File "<pyshell#26>", line 6, in fun1
    
18.     return fun1(a-b,b)
    
19.   File "<pyshell#26>", line 6, in fun1
    
20.     return fun1(a-b,b)
    
21.   [Previous line repeated 1021 more times]
    
22.   File "<pyshell#26>", line 2, in fun1
    
23.     if a == b:
    
24. RecursionError: maximum recursion depth exceeded in comparison

复制代码

跳转到最佳答案楼层

hrp

这不是递归吗

逃兵

有两个问题
1.运算时间非常的长
2.在运算数值较大时会超出了最大递归深度

1. >>> def fun1(a,b):
   
2.     if a == b:
   
3.         return a
   
4.     else:
   
5.         if a > b:
   
6.             return fun1(a-b,b)
   
7.         else:
   
8.             return fun1(a,b-a)
   
9. 
   
10.         
    
11. >>> fun1(9999,3)
    
12. Traceback (most recent call last):
    
13.   File "<pyshell#27>", line 1, in <module>
    
14.     fun1(9999,3)
    
15.   File "<pyshell#26>", line 6, in fun1
    
16.     return fun1(a-b,b)
    
17.   File "<pyshell#26>", line 6, in fun1
    
18.     return fun1(a-b,b)
    
19.   File "<pyshell#26>", line 6, in fun1
    
20.     return fun1(a-b,b)
    
21.   [Previous line repeated 1021 more times]
    
22.   File "<pyshell#26>", line 2, in fun1
    
23.     if a == b:
    
24. RecursionError: maximum recursion depth exceeded in comparison

复制代码

2012277033

没问题。。。。，实际上和辗转相除做法差不多，都是用的递归。

gonff

代码没问题，是环境递归深度的问题。

1. >>> import sys
   
2. >>> sys.getrecursionlimit()
   
3. 1000
   
4. >>> fun1(3001, 3)
   
5. Traceback (most recent call last):
   
6.   File "<pyshell#39>", line 1, in <module>
   
7.     fun1(3001, 3)
   
8.   File "<pyshell#1>", line 6, in fun1
   
9.     return fun1(a-b,b)
   
10.   File "<pyshell#1>", line 6, in fun1
    
11.     return fun1(a-b,b)
    
12.   File "<pyshell#1>", line 6, in fun1
    
13.     return fun1(a-b,b)
    
14.   [Previous line repeated 990 more times]
    
15.   File "<pyshell#1>", line 2, in fun1
    
16.     if a == b:
    
17. RecursionError: maximum recursion depth exceeded in comparison
    
18. >>> sys.setrecursionlimit(2000)
    
19. >>> fun1(3001, 3)
    
20. 1
    
21. >>> sys.getrecursionlimit()
    
22. 2000

复制代码

另外建议你改一下

1. def fun1(a,b):
   
2.     if a == 0:
   
3.         return a
   
4.     else:
   
5.         if a >= b:
   
6.             return fun1(a-b,b)
   
7.         else:
   
8.             return a

复制代码

这样的话整除时可以返回0，而不是b。