python - 如何摆脱大量的函数调用？

Question

如何摆脱大量的函数调用？下面是递归函数的一个例子：

def factorial(n):
    if n <= 1:
      return 1
    else:
      return n * factorial(n - 1)

我听说你可以很容易地用装饰器做到这一点，但我不知道如何使用它们

Answer 1

假设您已经仔细检查了您的算法并消除了任何冗余调用，您可以尝试以迭代方式重写您的函数（即使用循环而不是递归）。

递归通常可以以一种很好的方式表达对问题的解决方案，但是它相当消耗内存（在堆栈上反复保存状态）并且由于所有函数调用而不那么快。我看到它的主要好处在于它的表现力。

记忆化是另一种选择，因此您无需重新计算（调用函数），而是首先查看您之前是否已经计算（并存储）了一个值，然后使用它。

Answer 2

您正在寻找尾调用优化，这基本上是一种将递归程序转换为迭代而不重写它们的技术。例如，如果您使用 n = 1000 调用阶乘函数，Python 将无法抱怨“超出最大递归深度”。但是，当您将函数重写为尾递归时：

def tail_factorial(n, result=1):
    if n <= 1:
        return result
    else:
        return fac(n - 1, result * n)

然后用“蹦床”来称呼它：

def trampoline_factorial(n):

    def fac(n, result=1):
        if n <= 1:
            return result
        else:
            return lambda: fac(n - 1, result * n)

    f = fac(n)
    while callable(f):
        f = f()
    return f

你可以评价1000！没有任何问题。

尾调用优化确实可以在 Python 中使用装饰器实现自动化，参见例如这里