理解递归scala countchange函数的求值顺序

我有一个函数，在给定一个货币数量和一个硬币列表的情况下，计算零钱的数量。这个函数似乎通过了基本的单元测试，但如果我是完全诚实的话，我不完全理解它为什么工作。

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。

您可以按如下方式展开求值（顺序实际上并不重要，这是一个纯函数），使用求值顺序展开最左边的函数应用程序并求值整数加法：
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 + 0 3 函数的每个应用程序都有效地使用它所传递的参数的自己的副本。
这个评估顺序与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) 等等。。。所以技术上我的评估策略

def countChangeRec(money: Int, coins: List[Int]): Int =
  if (money == 0) 1
  else if (money > 0 && coins.nonEmpty) {
    val minusHead = money - coins.head
    val tail = coins.tail
    countChangeRec(minusHead, coins) + countChangeRec(money, tail)
  } else 0

因为两者之间没有依赖关系 minusHead 以及 tail ，我们可以对它们进行平行评估。
要知道的一件重要的事情是，如果一个表达式没有副作用（例如，使 var 或可变结构、执行i/o、进入无限循环或抛出异常（这包括scala中的5大类杂质）），任何与数据依赖性兼容的评估策略都会给出相同的结果。这包括并行化评估（包括将评估卸载到不同的计算机）和缓存结果。

理解递归scala countchange函数的求值顺序

1条答案

相关问题

热门标签

最新问答