Блог

Это пример кода 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, Но я не понимаю, как это работает, кто-нибудь может помочь мне понять, как здесь работает рекурсия?

Поскольку я не совсем уверен, о чем вы просите, это может быть слишком сложно.

В match :

• case Nil будет соответствовать (и только соответствовать) пустому списку
• case hd :: tl разрушит список (точный механизм того, как / почему это работает, выходит за рамки этого ответа), при этом значение hd является первым элементом списка, а значение tl является списком, содержащим каждый элемент после первого

Итак, продолжая работу с моделью замещения оценки, мы в конечном итоге получаем:

• foo(7, List(1, 2, -2, 2)) : список ( ls ) непустой, поэтому второе предложение match совпадает, и результат
• 1 * foo(6, List(2, -2, 2)) : список непустой, поэтому второе предложение match совпадает, и результат (после упрощения, поскольку умножение является ассоциативным)
• 1 * 2 * foo(5, List(-2, 2)) : список непустой, поэтому второе предложение match совпадает, и результат
• 1 * 2 * -2 * foo(4, List(2)) : список непустой, поэтому второе предложение 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 каждая из них будет полностью пересекать список).

Я добавил println к вашему первоначальному ответу, который печатает трассировку стека выполнения точно так, как Леви объяснил в своем ответе. Этот трюк должен помочь с другими рекурсивными примерами понять поток выполнения:

 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

*/



  

foo завершается, когда список, переданный в качестве параметра, ls является Nil (пустым).

При каждом foo вызове ls его head ( hd ) и tail ( tl ) извлекаются с помощью сопоставления с шаблоном. Заголовок умножается на следующий foo вызов, который принимает только конец списка (а также вычитает n значение на 1.

Когда foo(7,List(1,2,-2,2)) вычисляется, следующим шагом является 1 * foo(6, List(2, -2, 2)) и так далее…