Javascript 中递归函数的记忆

Question

我有这个递归函数，它接收一组纸牌并找到特定纸牌的索引：

const getCardIndex = (deck, fullCardName) => fullCardName === deck[0] ? 52 - deck.length : getCardIndex(deck.splice(1), fullCardName)

const deck = 'Ace of Hearts, Ace of Diamonds, Ace of Clubs, Ace of Spades, Two of Hearts, Two of Diamonds, Two of Clubs, Two of Spades, Three of Hearts, Three of Diamonds, Three of Clubs, Three of Spades, Four of Hearts, Four of Diamonds, Four of Clubs, Four of Spades, Five of Hearts, Five of Diamonds, Five of Clubs, Five of Spades, Six of Hearts, Six of Diamonds, Six of Clubs, Six of Spades, Seven of Hearts, Seven of Diamonds, Seven of Clubs, Seven of Spades, Eight of Hearts, Eight of Diamonds, Eight of Clubs, Eight of Spades, Nine of Hearts, Nine of Diamonds, Nine of Clubs, Nine of Spades, Ten of Hearts, Ten of Diamonds, Ten of Clubs, Ten of Spades, Jack of Hearts, Jack of Diamonds, Jack of Clubs, Jack of Spades, Queen of Hearts, Queen of Diamonds, Queen of Clubs, Queen of Spades, King of Hearts, King of Diamonds, King of Clubs, King of Spades'.split(', ')

const result = getCardIndex(deck, 'King of Spades')

console.log(result)

有什么方法可以加快速度，即使用记忆？

Answer 1

对于预先识别解决方案（O(52) = O(1)）然后可以在一次操作中查找解决方案的解决方案，放弃递归函数，将牌组变成一个对象，其键是卡名，值是卡索引，然后在对象上查找卡属性:

const deck = 'Ace of Hearts, Ace of Diamonds, Ace of Clubs, Ace of Spades, Two of Hearts, Two of Diamonds, Two of Clubs, Two of Spades, Three of Hearts, Three of Diamonds, Three of Clubs, Three of Spades, Four of Hearts, Four of Diamonds, Four of Clubs, Four of Spades, Five of Hearts, Five of Diamonds, Five of Clubs, Five of Spades, Six of Hearts, Six of Diamonds, Six of Clubs, Six of Spades, Seven of Hearts, Seven of Diamonds, Seven of Clubs, Seven of Spades, Eight of Hearts, Eight of Diamonds, Eight of Clubs, Eight of Spades, Nine of Hearts, Nine of Diamonds, Nine of Clubs, Nine of Spades, Ten of Hearts, Ten of Diamonds, Ten of Clubs, Ten of Spades, Jack of Hearts, Jack of Diamonds, Jack of Clubs, Jack of Spades, Queen of Hearts, Queen of Diamonds, Queen of Clubs, Queen of Spades, King of Hearts, King of Diamonds, King of Clubs, King of Spades'.split(', ')
const deckObj = Object.fromEntries(deck.map((str, i) => [str, i]));


console.log(deckObj['King of Spades'])
console.log(deckObj['Ace of Diamonds'])
console.log(deckObj['Queen of Diamonds'])

Answer 2

正如评论所暗示的那样，没有理由递归地执行此操作。 indexOf 很好地解决了这个问题。

但是，如果您决心编写递归解决方案，那么您的技术就有很大的问题。你正在破坏你试图搜索的对象！

Array.prototype.splice 是 破坏性的 。它改变了它工作的数组。最后，您将得到一个索引和一副几乎空的纸牌！

这完全有效几乎是巧合。如果您打算使用 slice，那将有效并且不会出现此问题。 slice 只是为您提供从一个索引开始到另一个索引结束（或在数组末尾）的数组副本。splice 做的更多。它删除元素的子列表，插入其他元素，然后 returns 删除的元素。如果你碰巧用一个起始索引调用它，它会删除数组的其余部分并 returns 它。所以调用 deck.slice(1) 和 deck.splice(1) 碰巧 return 是同一件事，但是第二个调用也删除了所有 returned 的项目来自你的数组。

因此，修复您的函数的最快方法就是：

const getCardIndex = (deck, fullCardName) => 
  fullCardName === deck[0] 
    ? 52 - deck.length 
    : getCardIndex (deck.slice(1), fullCardName)

但老实说，这毫无意义。它有效，但在每次递归调用时，它都会构建一个新数组，一个比以前版本更短的数组。对于一个简单的搜索来说，这是很多内存。

所以这是另一种仅在索引上递归的技术：

const getCardIndex = (deck, fullCardName, idx = 0) =>
  idx >= deck.length 
    ? -1
    : deck [idx] == fullCardName
      ? idx
      : getCardIndex (deck, fullCardName, idx + 1)

但是请注意，除了变量名称和函数之外，这里没有任何特定于套牌和纸牌的内容。所以我们可以将其转换为更通用的函数，如下所示：

const getIndex = (xs, x, idx = 0) =>
  idx >= xs.length 
    ? -1
    : xs [idx] == x
      ? idx
      : getIndex (xs, x, idx + 1)

我们有一个递归解决方案，用于查找任意数组中值的索引。

同样，没有理由使用此功能。这是学习递归的合理练习，但仅此而已。请改用 indexOf。

Javascript 中递归函数的记忆

Memoization of a recursive function in Javascript

javascript

recursion

memoization