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

当作为参数 ls 传递的列表为 Nil（空）时，

foo 终止。

每次调用 foo 时，ls 都会通过模式匹配提取其头部 (hd) 和尾部 (tl)。头部与下一个 foo 调用相乘，该调用仅采用列表的尾部（以及将 n 值减去 1.

当foo(7,List(1,2,-2,2))求值时，下一步就是1 * foo(6, List(2, -2, 2))等等...

Answer 2

由于我不完全确定你在问什么，这可能过于详细了。

在match:

case Nil 将匹配（且仅匹配）一个空列表
case hd :: tl 将解构列表（how/why 的确切机制超出了这个答案的范围），值 hd 是列表的第一个元素，并且值 tl 是包含第一个

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

foo(7, List(1, 2, -2, 2))：列表(ls)是non-empty，所以第二个match子句匹配，结果是
1 * foo(6, List(2, -2, 2))：列表为non-empty，所以匹配第二个match子句，结果为（简化后，因为乘法是结合的）
1 * 2 * foo(5, List(-2, 2))：列表为non-empty，所以第二个match子句匹配，结果为
1 * 2 * -2 * foo(4, List(2))：列表为non-empty，所以第二个match子句匹配，结果为
1 * 2 * -2 * 2 * foo(3, Nil)：列表为空，所以匹配第一个match子句，结果为
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 将各自完全遍历列表）。

Answer 3

我已将 println 添加到您的原始答案中，它会打印执行堆栈跟踪，就像 Levi 在他的答案中所解释的那样。这个技巧应该有助于其他递归示例来理解执行流程：

def printMul(xs: List[Int]) = if (xs.nonEmpty) xs.mkString(" * ") + " * " else ""

def foo(n: Int, ls: List[Int], prev: List[Int] = Nil): Int =
  ls match {
    case Nil =>
      println(s"${printMul(prev)}$n")
      n
    case hd :: tl =>
      println(s"${printMul(prev)}$hd * foo(${n - 1}, $tl)")
      hd * foo(n - 1, tl, prev :+ hd)
  }

// ====== Output ======
/*

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, List())
1 * 2 * -2 * 2 * 3

*/

Scala递归头尾模式匹配

Scala recursive head tail pattern match

scala

pattern-matching