简要介绍记忆法

由 Mux 主办的 DEV 全球展示挑战赛：展示你的项目！

如果你曾经看过《破解编程面试》（或其他任何算法书籍），你至少应该知道什么是记忆化以及它的用途。本文可以看作是该书摘录的更全面、更通俗易懂的 JavaScript 版本。

没有什么问题比求斐波那契数列更能解释（糟糕的）递归了n，所以让我们开始吧：

function fib(n) {
    if (n == 0 || n == 1) return n;
    return fib(n - 1) + fib(n - 2);
}

哦不，语法高亮对你不起作用？别担心，只有我遇到这个问题。在我看来，语法高亮对于阅读代码来说相当分散注意力，尤其是在代码这么短的时候。它在编写代码时很有帮助，但在阅读代码时，你应该专注于逻辑步骤，确保自己能够理解它们。

这很简单。一个递归函数，包含一个或多个基本情况（在本例中为当n == 0且仅当 x ≥ 0 时n == 1），以及递归结果。如果您完全不了解递归的工作原理，我建议您先简单阅读一下这篇文章：《递归入门》。 （别忘了点赞并关注我哦！写文章需要时间和精力！）

上述函数的问题fib在于它的运行时间呈指数级增长O(2^n)。这几乎是你能遇到的最糟糕的运行时间了。到底有多糟糕呢？如果你调用该函数fib(50)计算斐波那契数列的第50个数，并且需要一分钟才能返回结果，那么调用该函数fib(100)大约需要1,125,899,906,000,000分钟（向下取整到百万分之一），这相当于大约20亿年（有趣的是：到那时，我们的地球和半个太阳系应该早已被不断膨胀的太阳吞噬了）。

公平地说，这个问题本身就不是递归能解决的典型问题。以下这部分递归：

fib(n - 1) + fib(n - 2);

这意味着对于函数调用的每个N第 t 个节点，都会衍生出两个分支。更糟糕的是，对于每个N第 t 次调用，都会有重复执行的操作。下面是一个精心绘制的 ASCII 树状图，展示了实际发生的情况：

                           fib(5)
                        /          \
                   fib(4)           fib(3)
                 /       \          /      \
             fib(3)   fib(2)       fib(2)  fib(1)
           /    \    /     \      /     \
          /      \ fib(1) fib(0) fib(1) fib(0)
       fib(2) fib(1)
      /      \
    fib(1) fib(0)

如你所见，从fib(3)下往上完成的工作其实可以只做一次，而不是像现在这样重复计算。当 时N = 5，你会发现fib(N - 2)被计算了两次、fib(N - 3)三次。如果这种情况持续足够长的时间，假设N是一个很大的数字，比如 100，那么可以肯定的是……

对于每个fib(N)，fib(N - (N - p))将重复p多次，其中p ∈ {x | 2 < x < N}（p是元素range (2..N-1)）。说说行李吧！

记忆化 = 记住过去

听起来或许有些夸张，但这恰恰概括了这项技术的定义。想象一下，你的代码配备了人工智能功能，可以避免重复我们前面提到的那些工作。然而，人工智能仍然需要有办法记住已经完成的工作。在这种情况下，虚拟的人工智能帮不上什么忙。它能做的最明智的事情就是意识到这fib是一项自杀式任务，并从一开始就切换到记忆模式。

那么，我们的大脑快速记忆和回忆的最佳方式是什么呢？就是将它与其他事物联系起来。这正是关联数组（哈希映射、哈希表、字典）和数组的工作原理！

在我们的斐波那契数列例子中，我们可以使用两种数据结构，但数组更简单，因为键已经是整数了。

其理念是让fib函数“携带”一个存储过往记忆的数组，这样在其令人着迷的递归过程中，无论何时，它都能回忆起即将执行的工作实际上已经完成，只需简单地执行即可。具体实现方法如下：

function fib(n, brain = []) {
    if (n == 0 || n == 1) return n;

    // If brain has no memory of the work for fib(n)
    if (brain[n] == 0) {

        // compute and then memorize it
        brain[n] = fib(n - 1, brain) + fib(n - 2, brain); 
    }

    // just returns what's already memorized
    return brain[n];
}

现在，每当fib调用该函数时，它都会携带brain之前工作的信息，从而避免重复执行相同的操作。当然，这需要牺牲一定量的数组空间brain，但现在你可以在几毫秒内完成计算，fib(10000)而无需等待宇宙毁灭两次。

ps 至于我们“正念”的新运行时间，就留给你们自己去琢磨吧fib。

再见