递归 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) {&nbsp; console.log(amount, coins);&nbsp; if(amount == 0) return 1;&nbsp;&nbsp; let currentCoin = coins[coins.length - 1];&nbsp; console.log(':', currentCoin, amount);&nbsp; let total = 0;&nbsp; for(let qty = 0; qty * currentCoin <= amount; qty++){&nbsp; &nbsp; total += change(amount - qty * currentCoin, coins.slice(0, -1))&nbsp; &nbsp; console.log('=', total);&nbsp; }&nbsp; console.log('recdone');&nbsp; return total;};console.log(change(3,[2]))

Answer 2

var change = function(amount, coins) {&nbsp; &nbsp; if(amount == 0) return 1;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; let currentCoin = coins[coins.length - 1]; // firstpass 1-1 = 0, second pas 0-1=-1 => coins[-1] = undefined&nbsp;&nbsp; &nbsp; let total = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// this will 0*0<=3, second pass 0*undefined => null which is false hence never execute&nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; for(let qty = 0; qty * currentCoin <= amount; qty++){&nbsp; &nbsp; &nbsp; &nbsp; total += change(amount - qty * currentCoin, coins.slice(0, -1))&nbsp; &nbsp; }&nbsp; &nbsp; return total;};console.log(change(3,[2]))在第二遍时，coins.length = 0 然后let currentCoin = coins[0 - 1]; // = undefined&nbsp;稍后在 for 循环中，您将 0 * undefined ( qty * currentCoin) 导致 NaN 不是数字

Answer 3

不会崩溃，因为与数字相比，NaN 都是错误的... NaN < number or NaN > number 等等都会产生错误...所以qty * currentCoin <= amount评估为 false 并将从 for 中退出。所以，如果你需要检查 NaN 你必须在 forlet totalCoin = qty * currentCoin;let check = isNaN(totalCoin);if(check) {&nbsp; // return you sentinel value;}

Answer 4

在这种情况下不需要递归。可以使用自下而上的动态规划方法。让ways[i]表示i用给定硬币获得美元的方式数量，并coins[i]表示i第 th 个硬币的价值。然后，是从 1 到硬币数量的所有ways[i]的总和。ways[i - coins[j]]jvar change = function(amount, coins) {&nbsp; &nbsp; const ways = Array(amount + 1);&nbsp; &nbsp; ways[0] = 1;&nbsp; &nbsp; for(const coin of coins){&nbsp; &nbsp; &nbsp; for(let i = coin; i <= amount; i++){&nbsp; &nbsp; &nbsp; &nbsp; ways[i] = (ways[i] ?? 0) + ways[i - coin] ?? 0;&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return ways[amount];};console.log(change(5,[1,2,3,4,5]))