递归 for 循环上下文中的 NaN

Question

我试图理解我为一个问题找到的解决方案：“给你不同面额的硬币和总金额。编写一个函数来计算构成该金额的组合数量。你可以假设你有无限每种硬币的数量。”我的问题是，如果我使用 change(3,[2]) 运行该函数，为什么它会吐出 0。我无法理解在单个递归调用 currentCoin 之后如何变得未定义，然后当程序到达 for在该调用中循环，它不会再次使用total += change(amount - 0 * undefined, coins.slice(0, -1)). 为什么它不会因无限递归调用change(NaN,[])或coins.slice(0,-1)在空数组上使用而崩溃。在 for 循环中似乎忽略了这一点。我是否误解了 for 循环的工作原理？var change = function(amount, coins) {    if(amount == 0) return 1;         let currentCoin = coins[coins.length - 1];    let total = 0;    for(let qty = 0; qty * currentCoin <= amount; qty++){        total += change(amount - qty * currentCoin, coins.slice(0, -1))    }    return total;};console.log(change(3,[2]))

Answer 1

这里发生了几件事。

首先是 的行为coins[coins.length - 1]。在 Javascript 中，当您在该列表中不存在的索引处访问列表的元素时，索引器将返回undefined而不是与 anIndexOutOfBoundsException或类似内容一起崩溃。

二是qty * currentCoin <= amount。在currentCoin未定义的情况下（由于上述原因），qty * currentCoin将为NaN. 在 Javascript 中，任何NaN与另一个数字的比较都会按设计返回 false。（例如NaN <= anything是假的）。

把这一切放在一起，你会看到，在第一次递归时，coins数组将为空，这使得currentCoinNaN。这会导致qty * currentCoin <= currentAmount错误，从而导致循环短路（因此slice永远不会在空列表上调用）。由于循环永远不会执行，total因此仍将为 0，这就是返回的内容。这一直持续到qty * currentCoin <= amount在最外层递归中变为真，并且该循环退出时total仍然等于 0（因为它只添加了 0）。

如果您console.log在有关该功能的战略位置散布调用，那么正在发生的事情会变得更加清晰：

var change = function(amount, coins) {

  console.log(amount, coins);

  if(amount == 0) return 1; 

  let currentCoin = coins[coins.length - 1];

  console.log(':', currentCoin, amount);

  let total = 0;

  for(let qty = 0; qty * currentCoin <= amount; qty++){

    total += change(amount - qty * currentCoin, coins.slice(0, -1))

    console.log('=', total);

  }

  console.log('recdone');

  return total;

};

console.log(change(3,[2]))

Answer 2

var change = function(amount, coins) {

    if(amount == 0) return 1; 

    

    let currentCoin = coins[coins.length - 1]; // firstpass 1-1 = 0, second pas 0-1=-1 => coins[-1] = undefined 

    let total = 0;

                   // this will 0*0<=3, second pass 0*undefined => null which is false hence never execute      

    for(let qty = 0; qty * currentCoin <= amount; qty++){

        total += change(amount - qty * currentCoin, coins.slice(0, -1))

    }

    return total;

};

console.log(change(3,[2]))

在第二遍时，coins.length = 0 然后

let currentCoin = coins[0 - 1]; // = undefined 

稍后在 for 循环中，您将 0 * undefined ( qty * currentCoin) 导致 NaN 不是数字

Answer 3

不会崩溃，因为与数字相比，NaN 都是错误的... NaN < number or NaN > number 等等都会产生错误...所以

qty * currentCoin <= amount

评估为 false 并将从 for 中退出。

所以，如果你需要检查 NaN 你必须在 for

let totalCoin = qty * currentCoin;

let check = isNaN(totalCoin);

if(check) {

  // return you sentinel value;

}

Answer 4

在这种情况下不需要递归。可以使用自下而上的动态规划方法。让ways[i]表示i用给定硬币获得美元的方式数量，并coins[i]表示i第 th 个硬币的价值。然后，是从 1 到硬币数量的所有ways[i]的总和。ways[i - coins[j]]j

var change = function(amount, coins) {

    const ways = Array(amount + 1);

    ways[0] = 1;

    for(const coin of coins){

      for(let i = coin; i <= amount; i++){

        ways[i] = (ways[i] ?? 0) + ways[i - coin] ?? 0;

      }

    }

    return ways[amount];

};

console.log(change(5,[1,2,3,4,5]))