前端客栈

看下面的一个方法:

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

尝试把它运行起来，并且输入一个变量，例如30，你可能会注意到，可能你得需要稍微等待10几秒钟才能得到结果。

为什么会这样呢？但n=10时，你可以估算一下这个程序所需要的执行的次数。没错，其实它就一直在重复执行一些重复的命令。这是最低效率的Fibonacci数字的求解方法了。

让我们稍稍改动一下这个程序，如下：

previous = {0:1, 1:1}
def fibonacci(n):
    if previous.has_key(n):
        return previous[n]
    else:
        newValue = fibonacci(n-1) + fibonacci(n-2)
        previous[n] = newValue
        return newValue

运行一下看看，觉得有什么不同了吗？尝试输入n=100计算看看，是不是几乎瞬间就能得到结果。

就这样稍微改动一下，利用python的“字典”来保存n对应的值，并事先定义好n=0，n=1时候的值，当函数Fbonacci被调用，先检查字典中是否包含要计算的结果。如果有就立刻返回结果，不再做递归调用。若没有，就得计算新值，并且新值在函数返回前加入到字典中。这样改动之后，大大提高了fbonacci的效率，缩短了计算时间，应该是说瞬间结果就出来了。