Я смотрю на Scala уже около 3 недель. То, что я до сих пор узнал, довольно простое:
- Если вы хотите запачкать руки рекурсиями, Scala не даст вам возможности прокрасться!
- Вы можете наслаждаться двумя видами рекурсии: нормальной рекурсией и хвостовой рекурсией 🎈
Давайте посмотрим на их различия с помощью простой факториальной функции, сначала реализованной с помощью обычной рекурсии, а затем с помощью хвостовой рекурсии.
1. Факториал
Напомню, что факториал - это произведение целого числа и всех целых чисел под ним. Например, факториал пять (5 !) равен 120, потому что 5 * 4 * 3 * 2 * 1 = 120. В рекурсивных методах n будет вызывать себя до тех пор, пока он находит свой базовый вариант. Давайте более подробно рассмотрим, как обычная и хвостовая рекурсии реализуют факториал.
2. Нормальная рекурсия
Вот как мы реализуем факториал с обычной рекурсией:
def factorial(n: Int): Int = {
if (n <= 1) 1
else n * factorial(n - 1)
}
println(factorial(5)) // 120
Для запуска этой рекурсивной функции JVM виртуальной машины Java (поверх которой выполняется Scala) использует стек вызовов. Этот стек вызовов будет сохранять частичные результаты каждого рекурсивного вызова, так что, когда функция достигает своего базового случая, стек вызовов может вернуться к вычислению желаемого результата. Каждый вызов рекурсивной функции использует то, что мы называем кадром стека.
Давайте визуализируем этот стековый фрейм, добавив небольшие изменения в наш код:
def factorial(n: Int): Int =
if (n <= 1) 1
else {
println("Computing factorial of " + n + " - first recursive call of " + (n - 1))
val result = n * factorial(n - 1)
println("Computed factorial of " + n )
result
}
println(factorial(5)) // 120
Этот код не повлияет на результат, но, по крайней мере, мы сможем лучше понять, что происходит под деревом:
Таким образом, мы можем видеть весь стековый фрейм, необходимый JVM для вычисления желаемого результата.
Все идет нормально.
Проблемы начинаются, когда внутреннему стеку JVM не хватает памяти (потому что да, у него ограниченная память ... 💣)
Чтобы проиллюстрировать это, давайте попробуем реализовать println(factorial(4000))
💥💣💥💣💥💣💥💣💥💣💥💣💥💣💥💣💥💣💥💣💥💣💥💣💥💣💥💣💥💣
У нас сбой:
Exception in thread "main" java.lang.StackOverflowError
StackOverflowError. Игра закончена. Фрейм стека здесь слишком велик, у нас недостаточно памяти для решения factorial(4000) с обычной рекурсией.
Я уверен, вы понимаете, к чему мы здесь идем!
Да. Решение этой проблемы - использовать вместо нее хвостовую рекурсию.
3. Хвостовая рекурсия
Хвостовые рекурсии не относятся к проблеме перегруженных фреймов стека. Это почему? Благодаря их дизайну. Хвостовые рекурсии часто используют вспомогательные функции с аккумуляторами в качестве параметра. Опять же, почему? Это добавит вспомогательную рекурсивную функцию, в которой возвращаемое значение будет получено с помощью хвостового вызова. Ключ состоит в том, чтобы использовать рекурсивный вызов в качестве ПОСЛЕДНЕГО выражения на каждом пути кода.
Давайте посмотрим на нашу предыдущую факториальную функцию, на этот раз написанную с хвостовой рекурсией:
def factorialTail(n: Int): BigInt = {
def factorialHelper(x: Int, acc: BigInt): BigInt =
if (x <= 1) acc
else factorialHelper(x - 1, x * acc) // TAIL RECURSION = use a recursive call as the LAST expression
factorialHelper(n, 1)
}
Дополнительное примечание: мы используем BigInt, поскольку мы реализуем нашу функцию с n: In = 4000, который имеет тип BigInt.
Итак, здесь factorialHelper() реализует рекурсию.
Но почему factHelper не приводит к StackOverflow, хотя как вспомогательная функция также является рекурсией?
Благодаря использованию аккумулятора. Аккумулятор - это ПОСЛЕДНЕЕ выражение пути кода. Это позволит Scala сохранить один и тот же кадр стека для рекурсивных вызовов, в отличие от предыдущего примера, где Scala требовался новый кадр стека для каждой рекурсии.
Давайте разложим это на factorialTail(5), чтобы лучше визуализировать идею:
factorialTail(5) factorialHelper(5, 1) // 5 is not <= 1 so: else factorialHelper(4, 5 * 1) // 4 is not <= 1 so: else factorialHelper(3, 4 * 5 * 1) // 3 is not <= 1 so: else factorialHelper(2, 3 * 4 * 5 * 1) // 2 is not <= 1 so: else factorialHelper(1, 2 * 3 * 4 * 5 * 1) // 1 is <= 1 so true: we return acc: acc = 2 * 3 * 4 * 5 * 1 acc = 120 println(factorialTail(5)) // 120
Ключевым моментом здесь является то, что возвращаемое значение - это аккумулятор, то есть вызванное ПОСЛЕДНЕЕ выражение. Таким образом, аккумулятор здесь является фундаментальным, потому что он сохраняет промежуточный результат без перегрузки кадра стека.
🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈
Итак, теперь, если мы попытаемся запуститьprintln(factorial(4000)), это сработает! И это дает нам действительно БОЛЬШОЙ ИНТ.
🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈
Просто для удовольствия:
1828801951514065013314743175573919044217377710730439219706452695420895979797317736485037028687048410733644304156928557175467246186154355733394261561795699671674528483159731749881876093748280498041957651294872061055..........................................................
Последние слова:
- Всегда используйте хвостовую рекурсию вместо обычной !!!
- Учите Scala, это весело !!
- Также следует отметить этот действительно действительно хороший курс Scala по Udemy: Rock the JVM! Scala и функциональное программирование для начинающих .
Если вам понравился этот пост и он был полезен, нажмите в ладоши 👏 Удачного кодирования!
