简化递归函数

Question

所以，我一直在构建这个函数，但是如果我们在参数中输入一个大的数字，它似乎有点重

def heron(n):
    if n==0:
        return 2
    else:
        return (0.5*heron(n-1)+3/(heron(n-1))) 

我怎样才能简化它呢？我可以只调用函数一次而不是两次吗？谢谢大家!

Answer 1

如果您使用的是Python 3.9或更高版本，那么可以使用来自functools的@cache装饰器（请参见https://docs.python.org/3.9/library/functools.html）。这将节省以前对函数的调用，并将大大减少运行时间。结合使用@quamrana建议，您将得到以下结果：

from functools import cache

@cache
def heron(n):
    if n==0:
        return 2
    else:
        h = heron(n-1)
        return 0.5 * h + (3 / h)

Answer 2

您当前的实现似乎非常高效。这是因为每次使用n > 0输入函数时，函数本身会被调用2次

一种解决方案是，不要两次调用同一个函数，而是保存heron(n-1)的值，然后在两个地方都使用它。这样我们就可以得到O(n)或线性时间

例如：

def heron(n):
    if n==0:
        return 2
    else:
        heronPrev = heron(n-1)
        return 0.5 * heronPrev + 3 / heronPrev

一般的方法是一次性解决子问题、保存结果和重用。而不是每次需要值时都解决子问题

这部分引入了动态规划算法方法。如果你想看看这些，有两个很酷的问题，计算线性时间的斐波那契数，1/0背包问题，河内塔

Answer 3

一种简化方法是简单地而不是多次调用自己：

def heron(n):
    if n == 0:
        return 2
    else:
        h = heron(n - 1)
        return 0.5 * h + 3 / h