Устранение рекурсии хвоста - очень интересная функция, доступная в языках функционального программирования, таких как Haskell и Scala. Он делает рекурсивные вызовы функций почти так же быстро, как зацикливание.

В моей последней статье о функциях функционального программирования в Python я сказал, что map немного избыточен, учитывая существование List Computing, и не рисовал lambda Expressions в очень хороший свет тоже. Мне кажется, что я несправедливо относился к функциональному программированию в целом, так как мне оно нравится как элегантный способ структурирования программ. Это просто не очень хорошо сочетается со стилем и философией Python. В качестве офсайда я упомянул отсутствие рекурсивного удаления хвоста как еще одно спорное дизайнерское решение в реализации Python.

Честно говоря, я не совсем понимал, что такое Tail Recursive Elimination (TRE, с этого момента), когда писал это. Я знал, что это оптимизация, связанная с рекурсивными вызовами функций, и что она присутствует в Haskell, но не намного.

Поэтому я решил компенсировать это как можно лучше: изучив и написав об этом статью, чтобы с вами этого не случилось!

Что такое рекурсивные вызовы?

Мы говорим, что вызов функции рекурсивен, когда он выполняется внутри области действия вызываемой функции. По сути, это функция, вызывающая сама себя.

Многие проблемы (фактически любую проблему, которую вы можете решить с помощью циклов, и многие другие, которые вы не можете решить) можно решить путем рекурсивного вызова функции до тех пор, пока не будет выполнено определенное условие.
Например, вот функция Python, написанная как в императивном, так и в функциональном стиле:

Теоретически обе функции делают одно и то же: учитывая список и элемент, проверяют, присутствует ли элемент, и возвращают его как bool. Однако на более низком уровне вторая реализация выполняет множество вызовов функций и фактически не возвращается ни из одной из них до тех пор, пока не будет сделана последняя. Почему это проблема?

Мотивация для устранения рекурсии

Поскольку вызовы функций занимают место в стеке нашего компьютера, существует жесткое ограничение на то, сколько мы можем сделать, прежде чем столкнемся с переполнением стека: заполнение всего нашего стека. Мало того: поскольку каждый вызов функции начинается с настройки стека (отправка вещей в память и другие дорогостоящие операции), второй код выполняется намного медленнее.

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

К счастью для нас, кое-кто уже нашел решение этой проблемы, но сначала давайте кое-что проясним.

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

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

Например, вот две версии факториальной функции. Один из них хвостовой рекурсивный, а другой - нет.

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

Введение в устранение рекурсии хвоста

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

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

Независимо от того, компилируется ли наш код (как в C или Golang) или интерпретируется (как Python), он всегда заканчивается в форме инструкций машинного языка. Обычно они кодируются на ассемблере или других подобных языках, которые представляют самый низкий уровень абстракции и, следовательно, наиболее детальный контроль над памятью и оборудованием.

Вот что происходит при каждом вызове функции:

  • Все регистры - аппаратный эквивалент переменных, в которых хранятся данные - помещаются в стек (записываются в память, но не самым медленным из возможных способов).
  • Ваш компьютер начинает читать инструкции с другого адреса памяти (соответствующего первой строке кода вызываемой функции).
  • Код выполняется с этого адреса и далее, делая то, что на самом деле делает функция. Обычно меняют значения регистров определенным образом.
  • Все значения регистров выталкиваются / извлекаются обратно из стека, поэтому функция, к которой мы возвращаемся, возвращает свои данные.
  • Выполняется оператор return, и инструкции снова начинают считываться из предыдущей функции.

Шаги два и четыре требуют больших затрат времени, как и большинство операций с памятью. Каждое нажатие или нажатие обычно занимает в десять раз больше, чем «обычная» (имеющая дело только с регистрами) инструкция.
Однако, если эти шаги были пропущены, функция могла бы записывать значения в регистр, потенциально перезаписывая те, которые были записаны вызывающей функцией. Только представьте, что произойдет, если каждый раз, когда вы вызываете print, все ваши переменные меняются на произвольные значения.

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

  • Мы можем сохранить адрес памяти, с которого запускается функция, и вместо вызова функции просто переместить «считыватель памяти» обратно к нему в конце.
  • Мы можем сами записывать в регистры, зная, какие значения ожидала от нас предыдущая функция, без необходимости использовать стек для восстановления предыдущего состояния. Мы знаем, чего ожидает «предыдущая функция», потому что это точно такая же функция. Мало того: нам даже не нужно сохранять и восстанавливать регистры, которые мы не будем изменять.

Таким образом мы сможем избежать толкания наших регистров вперед и назад, что отнимает много времени. Но это еще не все - поскольку фактических вызовов функций не происходит (мы используем только операторы jump - перемещение нашего считывателя инструкций-), мы не заполняем наш стек, и переполнение стека никогда не может происходить. Во-первых, нам не нужно сохранять предыдущий контекст в стеке, потому что мы просто возвращаемся к одной и той же функции снова и снова. Единственный контекст, который нам нужно сохранить, - это контекст для первого вызова нашей функции.

Подводя итог, можно сказать, что TRE - это оптимизация, которая использует очень частный случай вызовов функций: функции вызывают сами себя и возвращают свой вывод без какой-либо дальнейшей обработки. Он использует знания, которые функция имеет о себе, так что она может записывать подходящие значения в соответствующие регистры, без необходимости восстанавливать те, в которые она не вносила никаких изменений во время своего выполнения. Затем он просто переходит к своему собственному началу, когда вызывает себя, без необходимости перемещать что-либо в стеке.

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

Вот очень удобный линейный поиск в Haskell, посмотрите, насколько элегантно он умещается всего в двух строках! (Тем, кто действительно хорошо разбирается в Haskell, простите, пожалуйста, мои плохие практики или ужасный код):

Я надеюсь, что теперь вы лучше понимаете, что такое TRE, и, возможно, о функциональных языках в целом. Если в этом объяснении есть какие-то части, которые, по вашему мнению, недостаточно ясны или слишком подробны, сообщите мне об этом в комментариях, так как я все еще учусь писать.

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