javascript - 理解内存的斐波那契函数

Question

该函数取自 here :

function fib(n,memo) {
   memo = memo || {}
   if (memo[n]) {
      return memo[n]
   }
   if (n <= 1) {
      return 1
   }
   return memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
}

这是一个有效的内存递归函数，它接受参数 n 并返回第 n: 个斐波那契数。

我无法理解的是，具有指定值的备忘录对象如何在不同的递归函数调用中可见？我认为下面的图片正确地描述了使用参数 4 调用该函数时所发生的情况，但如果不是，请纠正我:

Recursion chart

记下图中标有 1. 和 2. 的函数调用以及它们各自的注释。数字 2 (fib(1)) 是如何获得包含数字 1 (fib(2)) 中分配的值的备注参数的？提供给数字 2 (fib(1)) 的备忘录不应该与提供给其上方的 fib(3) 调用相同吗，这将是一个空对象？

我知道备忘录对象可能只是一个全局变量，并且对它的所有赋值都会在所有递归中自动可见，但我只是想了解这种特定技术的工作原理。

希望这个描述是有道理的。谢谢。

Answer 1

简介:为什么会这样？

您在评论中表示，按值传递描述有助于澄清这一点。但基本点是，在递归调用中，缓存是从外部传递给它们的。他们获得共享值引用的副本。初始调用接受缓存，如果未提供，则创建一个新缓存。

如果你愿意，你可以这样调用它:

const fibCache = {};

fib (5, fibCache) //=> 8

fib (7, fibCache) //=> 21

并且您不会重新计算 fib (2)、fib (3)、fib (4) 或 fib (5) 在第二次调用中。但必须保留它很烦人。下面我们创建一个辅助函数，让我们创建具有永久缓存的内存函数。

内存策略

这可能被认为是较低级别的内存。该函数会被内存，但仅限于初始调用及其生成的所有递归调用的长度。有多种方法可以内存函数，以便缓存在调用之间持续存在。

如果我们从像这样的非内存版本开始:

function fib1 (n) {
  if (n <= 1) {
    return 1
  }
  console .log (`Calculating fib1 (${n})`)
  return fib1 (n - 1) + fib1 (n - 2)
}

console .log (`fib1 (5) returns ${fib1 (5)}`)
console .log ('------')
console .log (`fib1 (5) returns ${fib1 (5)}`)

我们将得到如下输出:

Calculating fib1 (5)
Calculating fib1 (4)
Calculating fib1 (3)
Calculating fib1 (2)
Calculating fib1 (2)
Calculating fib1 (3)
Calculating fib1 (2)
fib1 (5) returns 8
------
Calculating fib1 (5)
Calculating fib1 (4)
Calculating fib1 (3)
Calculating fib1 (2)
Calculating fib1 (2)
Calculating fib1 (3)
Calculating fib1 (2)
fib1 (5) returns 8

显然，当我们尝试更大的值时会遇到问题。

使用您提供的版本:

function fib2 (n,memo) {
   memo = memo || {}
   if (memo[n]) {
      return memo[n]
   }
   if (n <= 1) {
      return 1
   }
   console .log (`Calculating fib2 (${n})`)
   return memo[n] = fib2 (n - 1, memo) + fib2 (n - 2, memo)
}

console .log (`fib2 (5) returns ${fib2 (5)}`)
console .log ('------')
console .log (`fib2 (5) returns ${fib2 (5)}`)

我们减少了这个，以便内部调用不再重复，但在外部调用之间，我们仍然重复:

Calculating fib2 (5)
Calculating fib2 (4)
Calculating fib2 (3)
Calculating fib2 (2)
fib2 (5) returns 8
------
Calculating fib2 (5)
Calculating fib2 (4)
Calculating fib2 (3)
Calculating fib2 (2)
fib2 (5) returns 8

如果我们可以将缓存存储在函数调用外部的某个地方，我们就可以制作一个根本不重复的版本:

const memoize = (fn) => {
  const cache = {}
  return function (x) {
    if (!(x in cache)) {
      cache [x] = fn (x)
    }
    return cache [x]
  }
}

const fib3 = memoize (function (n) {
  if (n <= 1) {
    return 1
  }
  console .log (`Calculating fib3 (${n})`)
  return fib3 (n - 1) + fib3 (n - 2)
})

console .log (`fib3 (5) returns ${fib3 (5)}`)
console .log ('------')
console .log (`fib3 (5) returns ${fib3 (5)}`)

Calculating fib3 (5)
Calculating fib3 (4)
Calculating fib3 (3)
Calculating fib3 (2)
fib3 (5) returns 8
------
fib3 (5) returns 8

这里，我们将缓存存储在通过调用 memoize 帮助器生成的闭包中。对于许多问题来说，这是一个更令人满意的版本。这也适用于没有递归但计算很耗时的情况。