Распространенная ошибка: рекурсия головы
В этом блоге я расскажу о распространенной ошибке, которую допускают разработчики при решении задач, а именно о игнорировании важности хвостовой рекурсии.
Кратко: что такое рекурсия?
Рекурсия – это процесс разбиения проблемы на подзадачи и последовательное решение этой подзадачи до тех пор, пока вы не найдете решение.
«Лук — это луковая шелуха с луковицей внутри». - Барри Шейн
Почему рекурсия вместо циклов?
Scala (FP) побуждает программистов пересмотреть использование рекурсии вместо цикла while. Цикл For и While приводит к побочным эффектам(обновлению некоторых переменных). Подробнее о ФП и побочных эффектах читайте в моем предыдущем блоге.
Голова против хвоста
Я закодировал две версии вычисления факториала числа, используя как начальную, так и хвостовую рекурсию, и перечислил проблему (Примечание: здесь не используются другие подходы).
Вызов является хвостовым рекурсивным, если последний оператор функции является просто вызовом функции и после его возврата ничего не нужно делать, т. е. возвращаемое значение немедленно возвращается из вызывающей функции, когда вызов возвращается. С другой стороны, в головной рекурсии все операции выполняются во время возврата или, скажем, последний оператор не является вызовом функции(изображение 1 слева, последний оператор является n раз вызовом функции, а не только вызов функции)
На изображении 2 ниже для начальной рекурсии вычисление выполняется при возврате из базового условия, тогда как для хвостовой рекурсии промежуточный итог отправляется с сигнатурой метода, и в конце вычисления не требуются. Оператор return и функция могут выйти из последнего вызова.
Оба приведенных выше кода приводят к одному и тому же результату, тогда ПОЧЕМУ НУЖНО?
В первом решении все вызовы функций хранятся в стеке, который занимает O(N) пространства и может стать неэффективным с точки зрения использования памяти для достижения глубины (базового случая) для вычисления ответа.
Принимая во внимание, что в хвостовой рекурсии, когда рекурсивный вызов является последним оператором, он может быть оптимизирован компиляторами, и новые кадры стека не создаются, а функция выполняется в постоянном пространстве памяти. Это делает хвостовую рекурсию более удобной для памяти и мощной.
Многие языки программирования предлагают аннотацию, чтобы проверить, является ли ваша функция хвостовой рекурсией или нет, например, scala предлагает аннотацию '@tailrec'
Краткое содержание
Устранение хвостовых вызовов снижает объемную сложность рекурсии с O(N) до O(1) и устраняет бесконечный рост стека вызовов.
Использованная литература:
[1]: https://stackoverflow.com/questions/33923/what-is-tail-recursion?noredirect=1&lq=1
