Scala recursive head tail pattern match

user_13463488 0
Viewed 310

This is a sample scala code-

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

If I pass foo(7,List(1,2,-2,2)) gives me -24 But I don't understand how this works, can anyone help me understand how the recursion works here?

pattern-matching scala
3 Answers

Since I'm not totally sure what you're asking, this may be overly elaborate.

In the match:

  • case Nil will match (and only match) an empty list
  • case hd :: tl will destructure the list (the exact mechanism of how/why this works is beyond the scope of this answer) with the value hd being the first element of the list and the value tl being a list containing every element after the first

So, proceeding with the substitution model of evaluation, we end up with:

  • foo(7, List(1, 2, -2, 2)): the list (ls) is non-empty, so the second match clause matches and the result is
  • 1 * foo(6, List(2, -2, 2)): the list is non-empty, so the second match clause matches and the result is (after simplifying because multiplication is associative)
  • 1 * 2 * foo(5, List(-2, 2)): the list is non-empty, so the second match clause matches and the result is
  • 1 * 2 * -2 * foo(4, List(2)): the list is non-empty, so the second match clause matches and the result is
  • 1 * 2 * -2 * 2 * foo(3, Nil): the list is empty, so the first match clause matches and the result is
  • 1 * 2 * -2 * 2 * 3: which when multiplied out is
  • -24

For some people, the logic of this function would be better expressed as

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

It could also be expressed, after a little algebraic manipulation as

(n - ls.length) * ls.product

Although for a List that will be slower than the recursive implementations (as .length and .product will each fully traverse the list).

user_56412440

I have added println's to your original answer which prints execution stack trace exactly like Levi has explained in his answer. This trick should help with other recursive examples to understand execution flow:

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

*/
user_56441200

foo terminates when the list passed as parameter ls is Nil (empty).

Every time foo is called, ls has its head (hd) and tail (tl) extracted via pattern matching. The head is multiplied against the next foo call which takes only the tail of the list (as well as subtracting the n value by 1.

When foo(7,List(1,2,-2,2)) is evaluated, the next step is 1 * foo(6, List(2, -2, 2)) and so on...

user_57256770
Related