先来看一个让人震撼的小故事，故事来自知乎问题PC用户的哪些行为让你当时就震惊了？。

同学在一个化妆品公司上班，旁边一个大妈（四十多岁）发给他一个exl表，让他在里面帮忙找一个经销商的资料。
表格里面大约有几百个客户资料，我同学直接筛选填入信息，然后没找到，就转头告诉大妈，说这个表里没有。
大妈很严厉的批评了我同学，说年轻人干工作一定要沉的住气，心浮气躁可不行。这才几分钟啊，我才看了二十行，你怎么就找完了。
同学过去一看，大妈在一行一行的精挑细选，顿时一身冷汗。把筛选办法告知后，大妈不但不领情，还召集办公司其他老职员，一起声讨我同学，我们平时都是这么找的，你肯定是偷工减料，我们找一个小时没找完，你几分钟就找完了。

不知道是否确有此事，不过看起来好吓人的样子。仔细想想，大多数人都是用以往的经验来分析遇见的新问题的。就上面的大妈而言，在接触计算机之前的几十年里，她面对的都是纸质的客户资料，此时，要查找某一客户资料，只能一行一行看下去了。

在简单字典树(Trie)的实现一文中，我们以单词输入自动提示为引子，简单介绍了字典树的实现。那么，字典树到底可以用于哪些场合呢？

1. 前缀匹配：给定字典库，输入一段字符，返回以该字符串为前缀的所有单词。
2. 字频统计：给出一段文本，统计其中指定单词出现的频数。

之前用python简单写了一下斐波那契数列的递归实现（如下），发现运行速度很慢。

1
2
3
4
5
6

def fib_direct(n):
    assert n > 0, 'invalid n'
    if n < 3:
        return n
    else:
        return fib_direct(n - 1) + fib_direct(n - 2)

然后大致分析了一下fib_direct(5)的递归调用过程，如下图：

可以看到多次重复调用，因此效率十分低。进一步，可以算出递归算法的时间复杂度。T(n) = T(n-1) + T(n-2)，用常系数线性齐次递推方程的解法，解出递推方程的特征根，特征根里最大的n次方就是它的时间复杂度O(1.618^n)，指数级增长。

为了避免重复调用，可以适当地做缓存，python的装饰器可以完美的完成这一任务。