Что может взорвать мой ноутбук в функции хвостовой рекурсии?

Question

Мне нужно сделать так, чтобы этот список группировался в два списка по нечетным и четным номерам индекса, начиная с 1, а не 0. У меня проблема с рекурсией бесконечности, как мне кажется, потому что время выполнения второй функции слишком много и мой ноутбук возьмет марс.

Первая функция с простой рекурсией работает нормально, но вторая, merge2, с хвостовой рекурсией вырывает мой компьютер.

Вот код:

// Simple recursion
def merge1(listA: List[String], listB: List[String]): List[String] = (listA, listB) match {
  case (Nil, Nil) => Nil
  case (head1 :: tail1, Nil) => head1 :: merge1(tail1, Nil)
  case (Nil, head2 :: tail2) => head2 :: merge1(Nil, tail2)
  case (head1 :: tail1, head2 :: tail2) => head1 + head2 :: merge1(tail1, tail2)
}

merge1 (List("a", "b", "c", "d"), List("e", "f", "g", "h", "i", "j"));

// Tail recursion
def merge2 (listA1: List[String], listB1: List[String]): List[String] = {
  def merge2Helper(listA: List[String], listB: List[String], listACC: List[String]): List[String] =
(listA, listB) match {
      case (Nil, Nil) => listACC
      case (head1 :: tail1, Nil) => merge2Helper(tail1, listB, listACC ::: List(head1))
      case (Nil, head2 :: tail2) => merge2Helper(tail2, listB, listACC ::: List(head2))
      case (head1 :: tail1, head2 :: tail2) => merge2Helper(tail1, tail2, listACC ::: List(head1 + head2))
}
  merge2Helper(listA1, listB1, Nil)
}

merge2 (List("a", "b", "c", "d"), List("e", "f", "g", "h", "i", "j"));

Answer 1

3-й случай неправильный, он снова передает тот же список, который только что был обработан.

Должно быть так:

@tailrec def merge2Helper(listA: List[String], listB: List[String], listACC: List[String]): List[String] =
(listA, listB) match {
      case (Nil, Nil) => listACC
      case (head1 :: tail1, Nil) => merge2Helper(tail1, listB, listACC ::: List(head1))
      case (Nil, head2 :: tail2) => merge2Helper(listA, tail2, listACC ::: List(head2))
      case (head1 :: tail1, head2 :: tail2) => merge2Helper(tail1, tail2, listACC ::: List(head1 + head2))
}

Вы также должны добавить аннотацию @tailrec, чтобы указать компилятору, что вы ожидаете, что функция будет хвостовой рекурсивной (и потерпит неудачу, если это не так), чтобы гарантировать, что вы не попадете в переполнение стека с длинными списками.