我有一个函数,在给定一个货币数量和一个硬币列表的情况下,计算零钱的数量。这个函数似乎通过了基本的单元测试,但如果我是完全诚实的话,我不完全理解它为什么工作。
def countChange(money: Int, coins: List[Int]): Int = {
def countChangeRec(money: Int, coins: List[Int]): Int = {
if (money == 0) 1
else if(money > 0 && coins.nonEmpty) {
countChangeRec(money - coins.head, coins) +
countChangeRec(money, coins.tail)
}
else 0
}
if(money == 0 || coins.isEmpty) 0
else countChangeRec(money, coins)
}
举一个有论点的基本例子 money = 4
以及 coins = List(1, 2)
我现在用下面的评估顺序返回2(这是不正确的)。 countChangeRec(4-1, List(1, 2)) + countChangeRec(4, List(2))
countChangeRec(3-1, List(1, 2)) + countChangeRec(4-2, List(2)) countChangeRec(2-1, List(1, 2)) + countChangeRec(2-2, List(2))
```
countChangeRec(1-1, List(1, 2)) // => 1 returns 1 since money = 0
+ countChangeRec(0, List(2)) // => 1 since money = 0
返回2//情况并非如此,因为函数实际返回3。
1条答案
按热度按时间e0bqpujr1#
您可以按如下方式展开求值(顺序实际上并不重要,这是一个纯函数),使用求值顺序展开最左边的函数应用程序并求值整数加法:
countChangeRec(4, List(1, 2))
countChangeRec(3, List(1, 2)) + countChangeRec(4, List(2))
countChangeRec(2, List(1, 2)) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))countChangeRec(1, List(1, 2)) + countChangeRec(2, List(2)) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
countChangeRec(0, List(1, 2)) + countChangeRec(1, List(2)) + countChangeRec(2, List(2)) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))1 + countChangeRec(1, List(2)) + countChangeRec(2, List(2)) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
1 + countChangeRec(-1, List(2)) + countChangeRec(2, List(2)) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))1 + 0 + countChangeRec(2, List(2)) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
1 + countChangeRec(2, List(2)) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))1 + countChangeRec(0, List(2)) + countChangeRec(2, Nil) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
1 + 1 + countChangeRec(2, Nil) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))2 + countChangeRec(2, Nil) + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
2 + 0 + countChangeRec(3, List(2)) + countChangeRec(4, List(2))2 + countChangeRec(3, List(2)) + countChangeRec(4, List(2))
2 + countChangeRec(1, List(2)) + countChangeRec(3, Nil) + countChangeRec(4, List(2))2 + countChangeRec(-1, List(2)) + countChangeRec(1, Nil) + countChangeRec(3, Nil) + countChangeRec(4, List(2))
2 + 0 + countChangeRec(1, Nil) + countChangeRec(3, Nil) + countChangeRec(4, List(2))2 + countChangeRec(1, Nil) + countChangeRec(3, Nil) + countChangeRec(4, List(2))
2 + 0 + countChangeRec(3, Nil) + countChangeRec(4, List(2))2 + countChangeRec(3, Nil) + countChangeRec(4, List(2))
2 + 0 + countChangeRec(4, List(2))2 + countChangeRec(4, List(2))
2 + countChangeRec(2, List(2)) + countChangeRec(4, Nil)2 + countChangeRec(0, List(2)) + countChangeRec(2, Nil) + countChangeRec(4, Nil)
2 + 1 + countChangeRec(2, Nil) + countChangeRec(4, Nil)3 + countChangeRec(2, Nil) + countChangeRec(4, Nil)
3 + 0 + countChangeRec(4, Nil)3 + countChangeRec(4, Nil)
3 + 03
函数的每个应用程序都有效地使用它所传递的参数的自己的副本。这个评估顺序与scala的非常相似。唯一的区别是,这可以有效地并行计算函数参数,而在scala中则类似于:
countChangeRec(4, List(1, 2))
countChangeRec(4-List(1, 2).head, List(1, 2)) + countChangeRec(4, List(1, 2).tail)
countChangeRec(4-1, List(1, 2)) + countChangeRec(4, List(1, 2).tail)countChangeRec(3, List(1, 2)) + countChangeRec(4, List(1, 2).tail)
等等。。。所以技术上我的评估策略因为两者之间没有依赖关系
minusHead
以及tail
,我们可以对它们进行平行评估。要知道的一件重要的事情是,如果一个表达式没有副作用(例如,使
var
或可变结构、执行i/o、进入无限循环或抛出异常(这包括scala中的5大类杂质)),任何与数据依赖性兼容的评估策略都会给出相同的结果。这包括并行化评估(包括将评估卸载到不同的计算机)和缓存结果。