<p>可以使用带<a href="https://en.wikipedia.org/wiki/Memoization" rel="nofollow noreferrer">memoization</a>的递归计算第n个斐波那契数</p>
<p><strong>为什么?</strong></p>
<p>例如:假设您要计算<code>fibonacci(5)</code>,那么您需要计算<code>fibonacci(4)</code>和<code>fibonacci(3)</code>。但是现在,对于<code>fibonacci(4)</code>,您需要计算<code>fibonacci(3)</code>和<code>fibonacci(2)</code>,依此类推。但是等等,当您完成计算<code>fibonacci(4)</code>分支时,您已经计算了3和2的所有斐波那契,因此当您从第一个递归调用返回到另一个分支(<code>fibonacci(3)</code>)时,您已经计算了它。那么,如果有一种方法可以存储这些计算,以便更快地访问它们呢?您可以使用<a href="https://www.python.org/dev/peps/pep-0318/" rel="nofollow noreferrer">Decorators</a>创建<a href="https://en.wikipedia.org/wiki/Memoization" rel="nofollow noreferrer">memoize</a>类(某种内存以避免重复计算):</p>
<p>这样,我们将把<code>fibonacci(k)</code>的每次计算都存储在<code>dict</code>上,每次调用之前我们都会检查它是否存在于字典中,如果<code>True</code>返回,或者计算它。这种方法更快、更准确</p>
<pre><code>class memoize:
def __init__(self, function):
self.f = function
self.memory = {}
def __call__(self, *args):
if args in self.memory:
return self.memory[args]
else:
value = self.f(*args)
self.memory[args] = value
return value
@memoize
def fib(n):
if n <= 1:
return n
else:
return fib(n-1) + fib(n-2)
r = fib(300)
print(r)
</code></pre>
<p><strong>输出:</strong></p>
<pre><code>222232244629420445529739893461909967206666939096499764990979600
</code></pre>
<p>只花了<code>0.2716239</code>秒</p>