Linear Recursion & Tail Recursion. В чем отличие.

Линейной рекурсией считается рекурсивный вызов функцией саму себя или другую функцию и при этом использование результата этого вызова в какой-то финальной операции, результат которой и будет результатом функции. Классический пример линейной рекурсии факториал:

def factorial(n: Int): Int =
   if (n == 0) 1 else n * factorial(n - 1)

Хвостовой рекурсией считается рекурсивный вызов функцией саму себя или другую функцию,результат которой и будет результатом этой функции, то есть результат внутреннего вызова больше не вступает ни в какую операцию. Хвостовая рекурсия это классическая подмена циклов рекурсией. Вот пример на том же факториале:

def factorial(n: Int): Int = {
    def loop(acc: Int, n: Int): Int = {
      if (n == 0) acc
      else loop(acc * n, n - 1)
    }
    loop(1, n)
}

В чем же смысл менять такое компактное определение функции на столь громоздкое? А смысл есть -- дело в том, что например в JVM есть ограничение для вызова линейной рекурсии -- это где-то 2000 итераций, после чего стек переполниться. Здесь нам и приходит на выручку хвостовая рекурсия, которая не имеет ограничения. То есть если у нас есть риск рекурсивных вызовов больше 2000, то нужно всегда применять хвостовую рекурсию.

Почему же происходит переполнение стека? Дело в том, что если результат внутреннего вызова из самой себя функции не вступает ни в какую другую операцию, то мы можем использовать тот же function’s stack frame, в случае линейной рекурсии под каждый циклический вызов создается свой фрейм.

В Scala существует возможность перестраховаться и гарантированное не создать случайно линейно рекурсии:

def factorial(n: Int): Int = {
    @tailrec // Так все ок
    def loop(acc: Int, n: Int): Int = {
      if (n == 0) acc
      else loop(acc * n, n - 1)
    }
    loop(1, n)
}

@tailrec // А так компилятор будет ругаться
def factorial(n: Int): Int =
   if (n == 0) 1 else n * factorial(n - 1)