Skip to content

Instantly share code, notes, and snippets.

@limboinf
Last active August 29, 2015 14:20
Show Gist options
  • Save limboinf/a8ea401eca61de41e18e to your computer and use it in GitHub Desktop.
Save limboinf/a8ea401eca61de41e18e to your computer and use it in GitHub Desktop.
Fibonacci decorator
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def memoize(f):
cache = {}
def helper(x):
if x not in cache:
cache[x] = f(x)
return cache[x]
return helper
@memoize
def fib(n):
if n in (0, 1):
return n
else:
return fib(n - 1) + fib(n - 2)
print fib(100)
"""
上面这个例子中,是一个斐波拉契数例的递归算法。我们知道,这个递归是相当没有效率的,因为会重复调用。
比如:我们要计算fib(5),于是其分解成fib(4) + fib(3),而fib(4)分解成fib(3)+fib(2),fib(3)又分解成fib(2)+fib(1)……
你可看到,基本上来说,fib(3), fib(2), fib(1)在整个递归过程中被调用了两次。
而我们用decorator,在调用函数前查询一下缓存,如果没有才调用了,有了就从缓存中返回值。
一下子,这个递归从二叉树式的递归成了线性的递归。
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment