Scala Language
Рекурсия

Рекурсия хвоста

Используя регулярную рекурсию, каждый рекурсивный вызов подталкивает другую запись в стек вызовов. Когда рекурсия завершена, приложение должно вытолкнуть каждую запись полностью назад. Если есть много рекурсивных вызовов функций, это может закончиться огромным стеком.

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

Регулярная рекурсия

Этот пример не является хвостовым рекурсивным, так как при рекурсивном вызове функция должна отслеживать умножение, которое необходимо выполнить с результатом после возврата вызова.

def fact(i : Int) : Int = {
   if(i <= 1) i
   else i * fact(i-1)
}

println(fact(5))

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

(fact 5)
(* 5 (fact 4))
(* 5 (* 4 (fact 3)))
(* 5 (* 4 (* 3 (fact 2))))
(* 5 (* 4 (* 3 (* 2 (fact 1)))))
(* 5 (* 4 (* 3 (* 2 (* 1 (fact 0))))))
(* 5 (* 4 (* 3 (* 2 (* 1 * 1)))))
(* 5 (* 4 (* 3 (* 2))))
(* 5 (* 4 (* 6)))
(* 5 (* 24))
120

Если мы попытаемся аннотировать этот пример с помощью @tailrec мы получим следующее сообщение об ошибке: could not optimize @tailrec annotated method fact: it contains a recursive call not in tail position

Рекурсия хвоста

В хвостовой рекурсии вы сначала выполняете свои вычисления, а затем выполняете рекурсивный вызов, передавая результаты вашего текущего шага на следующий рекурсивный шаг.

def fact_with_tailrec(i : Int) : Long = {
   @tailrec
   def fact_inside(i : Int, sum: Long) : Long = {
      if(i <= 1) sum
      else fact_inside(i-1,sum*i)
   }
   fact_inside(i,1)
}

println(fact_with_tailrec(5))

Напротив, трассировка стека для хвостового рекурсивного факториала выглядит следующим образом:

(fact_with_tailrec 5)
(fact_inside 5 1)
(fact_inside 4 5)
(fact_inside 3 20)
(fact_inside 2 60)
(fact_inside 1 120)

Существует только необходимость отслеживать один и тот же объем данных для каждого вызова функции fact_inside потому что функция просто возвращает значение, которое она получила до самого верха. Это означает, что даже если fact_with_tail 1000000 вызывается, ему требуется только то же пространство, что и fact_with_tail 3 . Это не относится к не-хвостовому рекурсивному вызову, и поскольку такие большие значения могут вызвать переполнение стека.

Бесступенчатая рекурсия с батутом (scala.util.control.TailCalls)

Очень часто возникает ошибка StackOverflowError при вызове рекурсивной функции. Стандартная библиотека Scala предлагает TailCall, чтобы избежать переполнения стека, используя объекты кучи и продолжения для сохранения локального состояния рекурсии.

Два примера из скаладока TailCalls

import scala.util.control.TailCalls._
    
def isEven(xs: List[Int]): TailRec[Boolean] =
  if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))
    
def isOdd(xs: List[Int]): TailRec[Boolean] =
  if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))

// Does this List contain an even number of elements?
isEven((1 to 100000).toList).result

def fib(n: Int): TailRec[Int] =
  if (n < 2) done(n) else for {
    x <- tailcall(fib(n - 1))
    y <- tailcall(fib(n - 2))
  } yield (x + y)

// What is the 40th entry of the Fibonacci series?
fib(40).result