有什么方法可以使递归函数更快? [英] Any way to make recursive functions faster?

问题描述

在对递归函数进行了一些研究后，我面临着矛盾:一方面以递归方式解决问题很优雅，而另一方面在实践中性能似乎很糟糕，并且递归调用的次数有限.

After some research about recursive functions i am facing contradiction: On one side solving problems in recursive way is elegant while on the other side in practice performance seems to be horrible and number of recursive calls is limited.

我知道默认情况下 Python 的递归深度限制为 1000，但是即使在一个简单的应用程序中，我在 40 - 50 次调用时的性能也很差.

I understand by default Pythons recursive depth is limited to 1000, however even in a simple application i get very bad performmance as early as 40 - 50 calls.

举个例子:

def fibonacci(n):
    if n == 1 or n == 0:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

我电脑上的这个简单的递归函数即使是低 n 也需要大量时间来求解.为了测试，我还编写了另一个函数:

This simple recursive function on my PC takes huge amount of time to solve even for low n. For testing i also wrote another function:

def fib_nonrecursive(n):
    fib_seq = [1, 1]
    for i in range(2, n+1):
        value = fib_seq[i-1] + fib_seq[i-2]
        fib_seq.append(value)        
    return fib_seq[i]

即使在大数字上，非递归方式也非常快，因此最终问题不可能是涉及的操作或数字的大小.所以我的问题是为什么递归方式这么慢，有没有办法让它更快?有没有办法扩大递归深度?

Non recursive way is very fast even on big numbers, so definitivly problem cannot be operations involved or size of numbers. So my question is why the recursive way is so slow and is there any way to make it faster? Is there any way to expand resursive depth?

编辑由于答案建议使用记忆化，我研究了它并在我的示例中实现了它:

EDIT Since answers suggested using memoization i looked into it and implemented it on my example:

def mem(f):
    memory = {}
    def inner_function(x):
        if x not in memory:            
            memory[x] = f(x)
            return memory[x]
        else:
            return memory[x]
    return inner_function

@mem
def fibonacci(n):
    if n == 1 or n == 0:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

相同的 mem(f) 可以与其他递归函数 f 一起使用.@mem 部分必须包含在 f 中才能作为参数传递给 mem()(参见装饰器")这是一种稍微高级的编码方式，但我没有发现更简单的方法是为给定的示例实现记忆.如果有更简单的实现方式，请纠正我.

Same mem(f) can be used with other recursive functions f. The @mem part must be included for f to be passed as argument to mem() (see "decorators") It is slightly advanced way to code but i didnt find an easier was to implement memoization for given example. If there is simpler way of implementation pls correct me.

推荐答案

忽略了 fibonacci() 是记忆化的教科书案例(这将使它更快)这一事实，深入而廉价" 递归根本不是 Python 中的东西.

Ignoring the fact that fibonacci() is a textbook case for memoization (which would make it much faster), "deep and cheap" recursion simply is not a thing in plain Python.

在许多语言中都存在尾调用消除.Python没有这个.在许多语言中，推送额外的堆栈帧非常便宜.在 Python 中不是这样.

In many languages there is tail-call elimination. Python doesn't have this. In many languages, pushing an additional stack frame is very cheap. Not so in Python.

找到存在问题的实际代码并不容易，这可能在某种程度上解释了为什么 Python 人员保持简单并始终创建具有完整调试能力的真实堆栈帧.在大多数 Python 应用程序中，对廉价和深度递归的需求并不多.

It's not so easy to find real-world code where this is a problem, which may go some way toward explaining why the Python folks have kept it simple and always create bona fide stack frames with full debugging ability. There's just not a lot of demand for cheap and deep recursion in most Python applications.

这篇关于有什么方法可以使递归函数更快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！