[已解决]关于第22讲，

hero533

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

def fun1(a,b):
    if a == b:
        return a
    else:
        if a > b:
            return fun1(a-b,b)
        else:
            return fun1(a,b-a)
print(fun1(5, 10))  

         嘿嘿

最佳答案

月排行榜 / 总排行榜

逃兵

2020-11-24 11:20:31

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

>>> def fun1(a,b):
    if a == b:
        return a
    else:
        if a > b:
            return fun1(a-b,b)
        else:
            return fun1(a,b-a)

        
>>> fun1(9999,3)
Traceback (most recent call last):
  File "<pyshell#27>", line 1, in <module>
    fun1(9999,3)
  File "<pyshell#26>", line 6, in fun1
    return fun1(a-b,b)
  File "<pyshell#26>", line 6, in fun1
    return fun1(a-b,b)
  File "<pyshell#26>", line 6, in fun1
    return fun1(a-b,b)
  [Previous line repeated 1021 more times]
  File "<pyshell#26>", line 2, in fun1
    if a == b:
RecursionError: maximum recursion depth exceeded in comparison

跳转到最佳答案楼层

hrp

这不是递归吗

逃兵

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

>>> def fun1(a,b):
    if a == b:
        return a
    else:
        if a > b:
            return fun1(a-b,b)
        else:
            return fun1(a,b-a)

        
>>> fun1(9999,3)
Traceback (most recent call last):
  File "<pyshell#27>", line 1, in <module>
    fun1(9999,3)
  File "<pyshell#26>", line 6, in fun1
    return fun1(a-b,b)
  File "<pyshell#26>", line 6, in fun1
    return fun1(a-b,b)
  File "<pyshell#26>", line 6, in fun1
    return fun1(a-b,b)
  [Previous line repeated 1021 more times]
  File "<pyshell#26>", line 2, in fun1
    if a == b:
RecursionError: maximum recursion depth exceeded in comparison

2012277033

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

gonff

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

>>> import sys
>>> sys.getrecursionlimit()
1000
>>> fun1(3001, 3)
Traceback (most recent call last):
  File "<pyshell#39>", line 1, in <module>
    fun1(3001, 3)
  File "<pyshell#1>", line 6, in fun1
    return fun1(a-b,b)
  File "<pyshell#1>", line 6, in fun1
    return fun1(a-b,b)
  File "<pyshell#1>", line 6, in fun1
    return fun1(a-b,b)
  [Previous line repeated 990 more times]
  File "<pyshell#1>", line 2, in fun1
    if a == b:
RecursionError: maximum recursion depth exceeded in comparison
>>> sys.setrecursionlimit(2000)
>>> fun1(3001, 3)
1
>>> sys.getrecursionlimit()
2000

另外建议你改一下

def fun1(a,b):
    if a == 0:
        return a
    else:
        if a >= b:
            return fun1(a-b,b)
        else:
            return a

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