Scala递归头尾模式匹配

Question

这是一个示例 Scala 代码-

def foo(n : Int, ls : List[Int]) : Int =
ls match {
    case Nil => n
    case hd :: tl => hd*foo(n-1,tl)
}

如果我通过 foo(7,List(1,2,-2,2))给我 -24 但我不明白这是如何工作的，有人可以帮助我了解递归是如何工作的吗？

Answer 1

由于我不完全确定您要问什么，因此这可能过于复杂。
在 match :

case Nil将匹配(并且仅匹配)一个空列表

case hd :: tl将使用值 hd 解构列表(如何/为什么工作的确切机制超出了本答案的范围)作为列表的第一个元素和值 tl是一个包含第一个

之后的每个元素的列表

因此，继续评估的替代模型，我们最终得到:

foo(7, List(1, 2, -2, 2)) :列表( ls )非空，所以第二个匹配子句匹配，结果是

1 * foo(6, List(2, -2, 2)) :列表非空，所以第二个匹配子句匹配，结果是(简化后，因为乘法是结合的)

1 * 2 * foo(5, List(-2, 2)) : 列表非空，所以第二个匹配子句匹配，结果为

1 * 2 * -2 * foo(4, List(2)) : 列表非空，所以第二个匹配子句匹配，结果为

1 * 2 * -2 * 2 * foo(3, Nil) : 列表为空，所以第一个匹配子句匹配，结果为

1 * 2 * -2 * 2 * 3 : 相乘后为

-24

对于某些人来说，这个函数的逻辑会更好地表达为

def foo(n: Int, ls: List[Int]): Int =
  if (ls.isEmpty) n
  else ls.head * foo(n - 1, ls.tail)

经过一些代数运算后，它也可以表示为

(n - ls.length) * ls.product

虽然对于 List这将比递归实现慢(因为 .length 和 .product 将分别完全遍历列表)。