Как избавиться от хвостовой рекурсии

Зона кода

Эту статью я написал несколько лет назад для другого сайта, но она так и не была опубликована. Тогда 7-я версия Java только-только появилась на свет, а 6-я была всё ещё актуальна. Статья адресована, тем, кто уже имеет некоторый опыт программирования на языке Java. Я решил стряхнуть с неё пыль и опубликовать: пусть будет!

Здравствуйте, уважаемый читатель! В своё время я задавался вопросом: оптимизирует ли компилятор Java хвостовую рекурсию? В этой статье мы обязательно ответим на этот вопрос, тем более, что сделать это совсем несложно. А заодно разберёмся с понятиями рекурсивного метода, рекурсии и хвостовой рекурсии.

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

Если в рекурсивном методе нерекурсивная ветвь отсутствует или ей никогда не передаётся управление, то теоретически такой метод будет вызываться бесконечно. На практике это приведёт к быстрому переполнению памяти и аварийному завершению программы.

Предположим теперь, что метод не содержит непосредственного вызова самого себя, но из него вызывается другой метод, из которого вызывается третий, и т. д. Наконец, из некоторого n-го метода вызываться первый. Такой процесс называется косвенной рекурсией. Обсуждение косвенной рекурсии выходит за рамки данной статьи.

А сейчас рассмотрим задачу нахождения суммы чисел от 0 до n. Как известно, существует формула, с помощью которой достаточно легко подсчитать данную сумму. Однако нас сейчас будет интересовать реализация метода, получающего результат путём непосредственного суммирования.

Очевидным решением задачи является следующий метод:

Однако мы найдём и неочевидное (и крайне нерациональное) решение задачи в виде следующего рекурсивного метода:

Разумеется, не стоит применять такой подход на практике; в данном случае метод recSu m() играет исключительно иллюстративную роль.

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

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

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

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

Хвостовая рекурсия — это частный случай рекурсии, при котором рекурсивный вызов единственен и является последней инструкцией метода. При этом метод, вызвавший “сам себя”, должен немедленно возвратить результат рекурсивного вызова, не производя над ним предварительно никаких преобразований. Разумеется, последнее требование относится только к методам, возвращающим значение, отличное от void .

Как мы видим, рекурсивный вызов является последней инструкцией метода recSum() . Однако этот метод возвращает результат рекурсивного вызова, увеличенный на значение переменной n , т. е. преобразованный. По этой причине рекурсия, реализованная в методе recSum() , не является хвостовой.

Для того чтобы преобразовать её в хвостовую, введём новую локальную переменную sum , в которой будут храниться промежуточные результаты суммирования. Значение этой переменной будет передаваться в новую версию нашего рекурсивного метода вместе со значением n .

Таким образом, наш метод теперь будет принимать два параметра:

Для того чтобы воспользоваться методом tailRecSum() , нужно вызвать его, передав ему в качестве второго значения 0. Например, следующая программа находит сумму чисел от 0 до 10:

Выполнение класса TailRecSumTest приведёт к выводу на консоль числа 55.

В общем виде метод, содержащий хвостовую рекурсию (и возвращающий значение, отличное от void ), можно описать, например, так:

Здесь рекурсивный метод recMeth() , возвращающий значение типа тип_возвр_знач , принимает параметры пар_1 , пар_2 , . пар_n , имеющие типы тип_1 , тип_2 , . тип_n соответственно. Последняя инструкция возвращает результат вызова методом самого себя с выражениями выр_1 , выр_2 , . выр_n в качестве параметров.

Переделаем этот метод в итеративный:

Как мы видим, переделка весьма простая: тело метода заключается в бесконечный цикл while , а инструкция return заменяется несколькими инструкциями присваивания. Их смысл состоит в том, чтобы присвоить параметрам пар_1 , пар_2 , . пар_n новые значения. Промежуточные переменные пар_2_ , пар_3_ , . пар_n_ вводятся для того, чтобы все выражения вычислялись со “старыми” значениями параметров. Конечно же предполагается, что имена промежуточных переменных в рамках метода IterMeth() уникальны.

Приведём, воспользовавшись рассмотренной схемой, метод tailRecSum() к итеративной форме:

Сравним теперь методы iter Sum() и formerTailRecSum() . Оба решают одну и ту же задачу, оба используют итерационный подход, но код второго метода по сравнению с первым просто ужасен! С первого взгляда на второй метод непросто понять, что он всего лишь суммирует числа от 0 до n.

Итак, мы переделали рекурсию из нехвостовой в хвостовую, после чего, применив формальный подход, избавились от рекурсии вообще. В результате мы получили код, качество которого сильно уступает коду, который изначально написан не “формально”, а “по-человечески”.

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

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

А во-вторых (и это, как раз, главное), хвостовая рекурсия обычно устраняется не во время написания исходного кода программы, а в процессе её компиляции.

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

Давайте теперь вернёмся к вопросу, заданному в самом начале статьи, и выясним, оптимизирует ли компилятор Java хвостовую рекурсию.

С этой целью сохраним приведённый выше код класса tailRecSumTest в файле с именем TailRecSumTest.java и скомпилируем его командой

В результате компиляции получаем файл TailRecSumTest.class , представляющий собой байт-код, т. е. набор низкоуровневых инструкций, выполняемых виртуальной машиной Java. Эти инструкции записаны в двоичном виде. Для того чтобы их прочитать, дизассемблируем байт-код командой

javap –c TailRecSumTest

На консоль будет выведен код методов, содержащихся в классе TailRecSumTest , в виде инструкций виртуальной машины. Нас будет интересовать только метод tailRecSum() :

Обратите внимание на инструкцию c меткой “ 12 ” (13-я строка). Это есть ни что иное, как вызов метода tailRecSum() , т. е. рекурсивный вызов!

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

Компиляторы императивных языков программирования (к каковым относится и Java) могут поддерживать оптимизацию хвостовой рекурсии, а могут и не поддерживать. В то же самое время компиляторы функциональных языков, как правило, хвостовую рекурсию оптимизируют. Это связано с тем, что так называемые “чистые функции”, являющиеся важными элементами функциональных языков, не поддерживают циклы.

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

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

Прежде всего, перепишем нашу программу (см. класс TailRecSumTest ) на языке Scala:

Сохраним приведённый код в файле TailRecSumTest.scala , после чего скомпилируем его командой

В итоге, получим два фала с байт-кодом: TailRecSumTest.class и TailRecSumTest$.class .

Можно, при желании, убедиться в том, что программа работает корректно, запустив её на выполнение командой

и получив в консоли ожидаемый результат 55.

Не вдаваясь в подробности, отметим, что байт-код метода tailRecSum() содержится в файле TailRecSumTest$.class . Дизассемблируем этот файл командой

javap -c TailRecSumTest$

Как и в прошлый раз, нас интересует только код метода tailRecSum() :

Мы видим, что, в отличие от предыдущего случая, в коде метода нет рекурсивных вызовов. Зато имеется инструкция goto , передающая управление из конца метода в его начало. Это говорит о том, что исходный рекурсивный код скомпилировался в итеративный!

Вывод: компилятор Scala оптимизирует хвостовую рекурсию.

Источник

Русские Блоги

Постепенно разбирайтесь в хвостовой рекурсии Scala на примерах

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

1.1 Рекурсия

1.1.1 Рекурсивное определение

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

1.1.2 Рекурсивные условия

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

Рекурсивно реализуйте факториальную функцию:

В листинге кода if(n Сегмент рекурсивного возврата, else Последняя часть — это рекурсивная прямая секция.

1.1.3 Недостатки рекурсии:

• Необходимо сохранить стек вызовов, например листинг кода 1-1, каждая рекурсия должна быть сохранена n*factorial(n-1) Информация о кадре стека. Если вызовов слишком много, это может вызвать переполнение стека.
• Эффективность будет относительно низкой. Рекурсия заключается в постоянном вызове самого себя. Если сам метод более сложен, эффективность самого вызова будет каждый раз низкой.

1.2 Хвостовая рекурсия

1.2.1 Определение

Определение хвостовой рекурсии относительно просто, а именно:Функция вызывает себя в конце тела функции, это называется хвостовой рекурсией.。

Мы можем понять хвостовую рекурсию вот так

• Все рекурсивные формы вызовов появляются в конце функции.
• Рекурсивный вызов — это последний оператор, выполняемый во всем теле функции, и его возвращаемое значение не является частью выражения.

1.2.2 Пример программы

Ниже мы используем режим хвостовой рекурсии для достижения указанного выше факториала.

Листинг кода 1-2

Мы можем сравнить листинг кода 1-1 и 1-2.
В 1–1 каждый рекурсивный вызов зависит от переменной n, поэтому это может быть только другая рекурсия.

В 1-2 функция factorial То, что возвращается каждый раз, является самим собой, не полагаясь ни на какое значение. Он каждый раз вычитает 1 из main, каждый раз умножает main на aggr, а затем вызывает эти два результата в качестве параметров следующего рекурсивного вызова.

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

1.3 Петля

Циклы могут решить большинство проблем накопления. Циклы могут завершать накопление и итерацию. Проблема относительно проста для решения, а идеи более последовательны и легки для понимания.

Как написать факторный цикл числа n

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

2. Перепишите (цикл, рекурсия К хвостовой рекурсии)

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

Рекурсия хвоста будет поддерживать одно или несколько кумулятивных значений ( aggregate ) Параметры и параметр итерации. Разбираем подробно

2.1 Итераторы и аккумуляторы

Кумулятивная величина параметра aggregate Накопите результаты, полученные в каждом цикле, и затем передайте их следующему вызову.

Итераторы, как и обычная рекурсия или циклы, меняются один раз после каждой рекурсии или цикла. (Например, i in for (i = 0; i aggregate Параметр (накопление), который накапливает результаты после каждого вызова, а другой параметр main называется итератором, и каждый вызов будет иметь значение 1. Когда выполняются условия возврата, возвращается кумулятивное значение.

2.3 Цикл (цикл while) преобразован в хвостовую рекурсию (хвостовую рекурсию)

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

2.3.1 Циклы и хвостовая рекурсия

Как упоминалось выше, итераторы и аккумуляторы, циклы и хвостовая рекурсия имеют эти две концепции.

ИтераторсАккумулятор

Каждый вызов хвостовой рекурсии будет накапливаться (или накапливать, накапливать, вычитать и т. Д.), А затем будет итератор для итерации, и аккумулятор для накопления результата итерации, а затем вызовет себя как параметр.

2.3.2 Пример хвостовой рекурсии для нахождения факториала n, как указано выше:

1. В примере цикла есть один var , Он действует как аккумулятор в каждом цикле, накапливая результаты каждой итерации, и каждый итерационный процесс m*i Процесса.

2. Хвостовая рекурсия — та же идея, но с main Как итератор, уменьшайте каждый раз 1 , Аналогично в петле i К aggr В качестве аккумулятора результат каждой кумулятивной итерации, аналогично циклу m 。

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

3. Конкретные примеры — углубление понимания

3.1 Пример 1 — Найдите последовательность Фибоначчи

• Обычное рекурсивное письмо (низкая производительность)

• Тираж (тиражирование)

Можно видеть, что aggr является аккумулятором, а затем присваивает накопленное значение следующему следующему, а текущее значение равно следующему. В каждом цикле новые значения назначаются текущему и следующему, а когда накопление завершено, возвращается значение next.

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

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

Здесь рекурсивный вызов обычного метода — это добавление двух исходных функций с задействованными переменными n, n-1, n-2.

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

Используйте хвостовую рекурсию и сопоставление с образцом. Каждый раз, когда вы вызываете себя, присваивайте next to current, затем накапливайте значения current и next для нового следующего значения и вызывайте следующий раунд. Это очень похоже на описанный выше цикл мысли. Но он более функциональный и устраняет var.

3.2 Пример алгоритма 2-loadBalance

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

• Я впервые использовал для цикла с return Для выполнения этого требования код выглядит следующим образом:

Я вызываю этот метод 10 000 раз в тестовой программе, и соотношение возвращаемых случайных узлов соответствует переданному соотношению.

Мышление：

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

Оптимизация хвостовой рекурсии

Большинство или почти все циклы for можно оптимизировать с помощью хвостовой рекурсии. Как можно оптимизировать приведенный выше код?

Идеи: Цикл for выше, каждое увеличение segment Индекс равен +1 один раз за цикл.Поэтому, когда мы проектируем хвостовую рекурсию, мы можем использовать один параметр для достижения той же функции, а другой параметр должен быть сгенерированным случайным числом.
Хорошо, давайте реализуем это

Мы видим, что при использовании хвостовой рекурсии код будет очень элегантным, теперь напишите тестовый класс для тестирования!

Как и выше, тест пройден! Это очень элегантно и чувствуется прелесть хвостовой рекурсии?

4. Оптимизация хвостовой рекурсии компилятором Scala

Scala оптимизирует формальную строгую хвостовую рекурсию. Для строгой хвостовой рекурсии аннотации не требуются.

@tailrec позволяет компилятору проверить, является ли функция хвостовой рекурсивной или нет, в противном случае он сообщит об ошибке

В частности, выполните анализ производительности на примере вычисления последовательности Фибоначчи выше.

Проведя вышеупомянутый тест времени и времени вызова, можно сделать вывод, что потребление производительности хвостовой рекурсии очень низкое, а скорость очень высокая.

4.1 Оптимизация компилятора хвостовой рекурсии

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

Компилятор scala обнаружит хвостовую рекурсию, оптимизирует ее и скомпилирует в шаблон цикла.

4.2 Ограничения рекурсии Scala Tail

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

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

5. Резюме

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

[Конец статьи, добро пожаловать на перепечатку, укажите источник]

Источник