Как именно работает хвостовая рекурсия?
Я почти понимаю, как работает хвостовая рекурсия и чем она отличается от обычной. Я только не понимаю, почему не требуется, чтобы стек запомнил свой адрес возврата.
После вызова функции в функции хвостовой рекурсии делать нечего, но для меня это не имеет смысла.
Компилятор просто может преобразовать это
Вы спросите, почему «стеку не требуется запоминать свой адрес возврата».
Я хотел бы все изменить. Это делает использование стека помнить обратный адрес. Хитрость в том, что функция, в которой происходит хвостовая рекурсия, имеет свой собственный адрес возврата в стеке, и когда она переходит к вызываемой функции, она будет рассматривать его как свой собственный адрес возврата.
Конкретно, без оптимизации хвостового вызова:
В этом случае при g вызове стек будет выглядеть так:
С другой стороны, с оптимизацией хвостового вызова:
В этом случае при g вызове стек будет выглядеть так:
Очевидно, что при g возврате он вернется в то место, откуда f был вызван.
EDIT : в приведенном выше примере используется случай, когда одна функция вызывает другую функцию. Механизм идентичен, когда функция вызывает сама себя.
Хвостовая рекурсия обычно может быть преобразована компилятором в цикл, особенно при использовании аккумуляторов.
компилируется во что-то вроде
В рекурсивной функции должны присутствовать два элемента:
«Обычная» рекурсивная функция сохраняет (2) в кадре стека.
Возвращаемые значения в обычной рекурсивной функции состоят из значений двух типов:
Посмотрим на ваш пример:
Кадр f (5) «хранит», например, результат своего собственного вычисления (5) и значение f (4). Если я вызываю factorial (5), непосредственно перед тем, как вызовы стека начинают сворачиваться, у меня есть:
100 КБ для вычисления факториала (100) и так далее.
Рекурсивная функция хвоста помещает (2) в свои аргументы.
В хвостовой рекурсии я передаю результат частичных вычислений в каждом рекурсивном кадре в следующий, используя параметры. Давайте посмотрим на наш факторный пример Tail Recursive:
Посмотрим на его кадры в factorial (4):
Шаблоны рекурсии
Обычная рекурсивная функция выглядит следующим образом:
Чтобы преобразовать его в хвостовую рекурсию, мы:
Оптимизация хвостового вызова
Ваш компилятор должен оптимизировать его, или нет.
Что такое хвостовая рекурсия?
начиная изучать lisp, я столкнулся с термином хвост-рекурсивный. Что это значит?
23 ответов
рассмотрим простую функцию, которая добавляет N целых чисел. (например, sum(5) = 1 + 2 + 3 + 4 + 5 = 15 ).
вот простая реализация JavaScript, которая использует рекурсию:
обратите внимание, как каждый рекурсивный вызов должен завершиться, прежде чем интерпретатор JavaScript начнет фактически выполнять работу по вычислению суммы.
вот хвост-рекурсивная версия та же функция:
в хвостовом рекурсивном случае с каждой оценкой рекурсивного вызова running_total обновляется.
Примечание: В исходном ответе использовались примеры из Python. Они были изменены на JavaScript, так как современные интерпретаторы JavaScript поддерживают хвост вызовите оптимизацию но интерпретаторы Python этого не делают.
на традиционный рекурсии, типичная модель заключается в том, что вы сначала выполняете рекурсивные вызовы, а затем берете возвращаемое значение рекурсивного вызова и вычисляете результат. Таким образом, вы не получите результат вычисления, пока не вернетесь из каждого рекурсивного вызова.
следствием этого является то, что как только вы будете готовы выполнить следующий рекурсивный шаг, вам больше не нужен текущий кадр стека. Это позволяет оптимизировать. Фактически, с соответствующим написанным компилятором у вас никогда не должно быть переполнения стека прыскают с хвостовым рекурсивным вызовом. Просто повторно использовать текущий кадр стека для следующего рекурсивного шага. Я почти уверен, что это делает Lisp.
важным моментом является то, что хвостовая рекурсия-это, по сути, эквивалентные циклы. Это не просто вопрос оптимизации компилятора, но фундаментальный факт о выразительности. Это происходит в обоих направлениях: вы можете взять любой цикл формы
здесь E и Q выражения и S представляет собой последовательность операторов и превращает ее в хвостовую рекурсивную функцию
эквивалентно хвостовой рекурсивной функции(функциям)
(эта «обертка» хвостовой рекурсивной функции с функцией с меньшим количеством параметров является общей функциональной идиомой.)
этот отрывок из книги программирование в Lua показывает как сделать правильную хвостовую рекурсию (в Lua, но также должен применяться к Lisp) и почему это лучше.
A хвост вызов [хвостовая рекурсия] вид Гото одет как зов. Хвостовой вызов происходит, когда функция вызывает другой как последний действие, поэтому ему больше нечего делать. Например, в следующем коде, вызов g хвост звоните:
потому что правильный хвостовой вызов не использует космос стога, никакой предел на количество» вложенных » хвостовых вызовов, которые a программу можно сделать. Для например, мы можем вызовите следующую функцию с любым число как аргумент; оно никогда не будет переполнение стека:
. Как я сказал ранее, хвостовой вызов-это вида Гото. Как таковой, довольно полезный применение правильных хвостовых вызовов в Lua для программирования государственных машин. Такие приложения могут представлять каждый состояние функцией; изменить состояние перейти к (или позвонить) конкретному функция. В качестве примера приведем рассмотрим простую игру лабиринт. Этот лабиринт имеет несколько комнат, каждая с четыре двери: северная, южная, восточная и запад. На каждом шаге пользователь вводит направление движения. Если есть дверь в этом направлении, пользователь переходит к соответствующая комната; в противном случае программа выводит предупреждение. Цель перейти от начальной комнаты к финальной комната.
эта игра является типичной государственной машиной, где текущая комната-это состояние. Мы можем реализовать такой лабиринт с помощью одного функция для каждой комнаты. Мы используем хвост звонки для перемещения из одной комнаты в другую другой. Небольшой лабиринт с четырьмя комнатами может выглядеть так:
Итак, вы видите, когда вы делаете рекурсивный вызов как:
это не хвост рекурсивный, потому что у вас все еще есть дела (добавить 1) в этой функции после рекурсивного вызова. Если вы введете очень большое число, это, вероятно, вызовет переполнение стека.
используя регулярную рекурсию, каждый рекурсивный вызов толкает другую запись в стек вызовов. Когда рекурсия будет завершена, приложение затем должно вытащить каждую запись полностью вниз.
с хвостовой рекурсией компилятор может свернуть стек до одной записи, поэтому вы экономите пространство стека. Большой рекурсивный запрос может вызвать переполнение стека.
в основном хвостовые рекурсии могут быть оптимизированы в итерации.
вместо того, чтобы объяснять это словами, Вот пример. Это версия схемы факториальной функции:
вот версия факториала, которая является хвостовой рекурсивной:
в первой версии вы заметите, что рекурсивный вызов факта подается в выражение умножения, и поэтому состояние должно быть сохранено в стеке при выполнении рекурсивного вызова. В хвост-рекурсивной версии нет другого s-выражения ждем значение рекурсивного вызова, и поскольку больше нет никакой работы, состояние не нужно сохранять в стеке. Как правило, хвостовые рекурсивные функции схемы используют постоянное пространство стека.
в файле жаргона есть это, чтобы сказать об определении хвостовой рекурсии:
хвостовая рекурсия / n./
Если вы еще не устали от этого, см. рекурсию хвоста.
хвостовая рекурсия относится к рекурсивному вызову, являющемуся последним в последней логической инструкции в рекурсивном алгоритме.
обычно в рекурсии у вас есть базовый что останавливает рекурсивные вызовы и начинает выскакивать стек вызовов. Чтобы использовать классический пример, хотя больше C-ish, чем Lisp, факториальная функция иллюстрирует хвостовую рекурсию. Рекурсивный вызов происходит после проверка базы-условие.
Примечание., начальный вызов факториала должен быть факториалом (n, 1), где n-число, для которого факториал должен быть вычислен.
Это означает, что вместо того, чтобы нажимать указатель инструкции на стеке, вы можете просто перейти к вершине рекурсивной функции и продолжить выполнение. Это позволяет функциям рекурсировать бесконечно без переполнения стека.
Я написал блог сообщение по этому вопросу, в котором есть графические примеры того, как выглядят кадры стека.
вот быстрый фрагмент кода, сравнивающий две функции. Первая-традиционная рекурсия для нахождения факториала заданного числа. Второй использует хвостовую рекурсию.
очень простой и понятный для понимания.
простой способ определить, является ли рекурсивная функция хвостовой рекурсивной, если она возвращает конкретное значение в базовом случае. Это означает, что он не возвращает 1 или true или что-то в этом роде. Это, скорее всего, вернет какой-то вариант одного из методов парамтеры.
другой способ-сказать, свободен ли рекурсивный вызов от любого сложения, арифметики, модификации и т. д. Смысл его ничего, кроме чисто рекурсивный вызов.
в Java, вот возможная хвостовая рекурсивная реализация функции Фибоначчи:
сравните это со стандартной рекурсивной реализацией:
сравнение примеров, приведенных в Python:
этот момент важен, потому что хвостовая рекурсия, как видно здесь, не заставляет память расти, потому что, когда базовая VM видит функцию, вызывающую себя в хвостовой позиции( последнее выражение, которое будет оценено в функции), она устраняет текущий кадр стека, который известен как оптимизация хвостового вызова(TCO).
редактировать
NB. Имейте в виду, что приведенный выше пример написан на Python, среда выполнения которого не поддерживает TCO. Это просто пример, чтобы объяснить суть. TCO поддерживается на таких языках, как Scheme, Haskell etc
и тогда для удовольствия вы можете попробовать (format nil «
короче говоря, хвостовая рекурсия имеет рекурсивный вызов как последние оператор в функции, так что ему не нужно ждать рекурсивного вызова.
Это не хвост-рекурсивный способ написание вышеуказанной факторной функции (хотя некоторые компиляторы C++ могут все равно ее оптимизировать).
Зона кода
Эту статью я написал несколько лет назад для другого сайта, но она так и не была опубликована. Тогда 7-я версия Java только-только появилась на свет, а 6-я была всё ещё актуальна. Статья адресована, тем, кто уже имеет некоторый опыт программирования на языке Java. Я решил стряхнуть с неё пыль и опубликовать: пусть будет!
Здравствуйте, уважаемый читатель! В своё время я задавался вопросом: оптимизирует ли компилятор Java хвостовую рекурсию? В этой статье мы обязательно ответим на этот вопрос, тем более, что сделать это совсем несложно. А заодно разберёмся с понятиями рекурсивного метода, рекурсии и хвостовой рекурсии.
Рекурсивный метод — это метод, который вызывает сам себя. Такой вызов называется рекурсивным вызовом или рекурсией. Рекурсивный метод обязательно должен содержать, по крайней мере, одну нерекурсивную ветвь, т. е. ветвь, не содержащую рекурсивного вызова, причём цепочка рекурсивных вызовов всегда должна завершаться выполнением такой ветви.
Если в рекурсивном методе нерекурсивная ветвь отсутствует или ей никогда не передаётся управление, то теоретически такой метод будет вызываться бесконечно. На практике это приведёт к быстрому переполнению памяти и аварийному завершению программы.
Предположим теперь, что метод не содержит непосредственного вызова самого себя, но из него вызывается другой метод, из которого вызывается третий, и т. д. Наконец, из некоторого n-го метода вызываться первый. Такой процесс называется косвенной рекурсией. Обсуждение косвенной рекурсии выходит за рамки данной статьи.
А сейчас рассмотрим задачу нахождения суммы чисел от 0 до n. Как известно, существует формула, с помощью которой достаточно легко подсчитать данную сумму. Однако нас сейчас будет интересовать реализация метода, получающего результат путём непосредственного суммирования.
Очевидным решением задачи является следующий метод:
Однако мы найдём и неочевидное (и крайне нерациональное) решение задачи в виде следующего рекурсивного метода:
Разумеется, не стоит применять такой подход на практике; в данном случае метод recSu m() играет исключительно иллюстративную роль.
Вообще, итеративный (т. е. использующий цикл) способ решения задачи в большинстве случаев является более предпочтительным, чем рекурсивный. Это связано с тем, что при каждом вызове метода выделяется память для хранения его локальных переменных. Таким образом, чем длиннее цепочка рекурсивных вызовов, тем больше памяти требуется для корректной работы рекурсивного метода. Кроме того, само выделение памяти может требовать сравнительно немалых временных затрат.
В то же самое время, большое количество алгоритмов достаточно просто и понятно описываются, а значит, и программируются с привлечением рекурсии. Например, несложно запрограммировать рекурсивную реализацию метода быстрой сортировки.
А вот задача преобразования рекурсивного кода в итерационный может оказаться весьма нетривиальной. Так, для того, чтобы написать итеративную версию метода быстрой сортировки нужно изрядно поломать голову.
Однако в некоторых случаях переход от рекурсивной версии кода к итеративной настолько прост, что его можно легко формализовать. Сказанное относится, например, к случаю, так называемой, хвостовой рекурсии.
Таким образом, наш метод теперь будет принимать два параметра:
Выполнение класса TailRecSumTest приведёт к выводу на консоль числа 55.
В общем виде метод, содержащий хвостовую рекурсию (и возвращающий значение, отличное от void ), можно описать, например, так:
Переделаем этот метод в итеративный:
Приведём, воспользовавшись рассмотренной схемой, метод tailRecSum() к итеративной форме:
Итак, мы переделали рекурсию из нехвостовой в хвостовую, после чего, применив формальный подход, избавились от рекурсии вообще. В результате мы получили код, качество которого сильно уступает коду, который изначально написан не “формально”, а “по-человечески”.
Возникает резонный вопрос. Чем вообще интересна хвостовая рекурсия? Выглядит она нередко более запутанно, чем нехвостовая, а формальный переход от хвостовой рекурсии к итерации часто порождает отвратительный код.
Ответ заключается в следующем. Во-первых, наш формальный переход, конечно же, не идеален. Его можно улучшить (при этом усложнив его). Но это не главное.
А во-вторых (и это, как раз, главное), хвостовая рекурсия обычно устраняется не во время написания исходного кода программы, а в процессе её компиляции.
Дело в том, что некоторые компиляторы выполняют так называемую оптимизацию хвостовой рекурсии, генерируя низкоуровневый код, в котором рекурсия заменяется итерацией. Такая оптимизация приводит к экономии памяти и уменьшению времени работы программы и представляется вполне уместной.
Давайте теперь вернёмся к вопросу, заданному в самом начале статьи, и выясним, оптимизирует ли компилятор Java хвостовую рекурсию.
С этой целью сохраним приведённый выше код класса tailRecSumTest в файле с именем TailRecSumTest.java и скомпилируем его командой
javap –c TailRecSumTest
Что ж, ответ на интересовавший наш вопрос получен: компилятор Java не оптимизирует хвостовую рекурсию. Это означает, что особого смысла использовать исключительно хвостовую рекурсию при программировании на Java нет. Если же мы хотим оптимизировать рекурсию, то мы должны приводить её к итерации или сразу же писать программу в итеративном, а не рекурсивном стиле.
Компиляторы императивных языков программирования (к каковым относится и Java) могут поддерживать оптимизацию хвостовой рекурсии, а могут и не поддерживать. В то же самое время компиляторы функциональных языков, как правило, хвостовую рекурсию оптимизируют. Это связано с тем, что так называемые “чистые функции”, являющиеся важными элементами функциональных языков, не поддерживают циклы.
Таким образом, многократные повторения однотипных действий, осуществляющиеся в императивных языках с помощью циклов, в чистых функциях реализуются посредством рекурсий. По этой причине рекурсия в программах, написанных на функциональных языках, встречается достаточно часто.
Рассмотрим язык Scala, поддерживающий, в отличие от Java, функциональную парадигму программирования. Этот язык интересен для нас тем, что он имеет компилятор, генерирующий байт-код виртуальной машины Java. Значит, мы можем выяснить, поддерживает ли этот компилятор оптимизацию хвостовой рекурсии таким же способом, каким мы выясняли это для компилятора Java.
Прежде всего, перепишем нашу программу (см. класс TailRecSumTest ) на языке Scala:
Можно, при желании, убедиться в том, что программа работает корректно, запустив её на выполнение командой
и получив в консоли ожидаемый результат 55.
Как и в прошлый раз, нас интересует только код метода tailRecSum() :
Вывод: компилятор Scala оптимизирует хвостовую рекурсию.
Русские Блоги
Постепенно разбирайтесь в хвостовой рекурсии Scala на примерах
1. Рекурсия и хвостовая рекурсия
1.1 Рекурсия
1.1.1 Рекурсивное определение
Все знакомы с рекурсией. Функция, которая вызывает себя прямо или косвенно, называется рекурсией. Обычно он преобразует большую и сложную проблему в меньшую проблему, аналогичную решаемой исходной проблеме.Рекурсивная стратегия может выполнять несколько повторяющихся вычислений с небольшим объемом кода.
1.1.2 Рекурсивные условия
Вообще говоря, для рекурсии требуются граничные условия, рекурсивный прямой сегмент и рекурсивный возвратный сегмент. Если граничные условия не выполняются, рекурсивно двигаться вперед; когда граничные условия выполнены, возвращаться рекурсивно.
Рекурсивно реализуйте факториальную функцию:
1.1.3 Недостатки рекурсии:
1.2 Хвостовая рекурсия
1.2.1 Определение
Определение хвостовой рекурсии относительно просто, а именно:Функция вызывает себя в конце тела функции, это называется хвостовой рекурсией.。
Мы можем понять хвостовую рекурсию вот так
1.2.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) преобразован в хвостовую рекурсию (хвостовую рекурсию)
2.3.1 Циклы и хвостовая рекурсия
Как упоминалось выше, итераторы и аккумуляторы, циклы и хвостовая рекурсия имеют эти две концепции.
ИтераторсАккумулятор
Каждый вызов хвостовой рекурсии будет накапливаться (или накапливать, накапливать, вычитать и т. Д.), А затем будет итератор для итерации, и аккумулятор для накопления результата итерации, а затем вызовет себя как параметр.
2.3.2 Пример хвостовой рекурсии для нахождения факториала n, как указано выше:
Можно видеть, что aggr является аккумулятором, а затем присваивает накопленное значение следующему следующему, а текущее значение равно следующему. В каждом цикле новые значения назначаются текущему и следующему, а когда накопление завершено, возвращается значение next.
Тщательно проанализируйте вышеуказанный обычный цикл, каждый раунд из двух значений изменяется, а затем еще один накопитель, чтобы накопить эти два значения и присвоить его следующему большему, а затем перейти в следующий цикл.
Для хвостовой рекурсии мы делаем то же самое, определяем два принятых значения, текущее и следующее, а затем нуждаемся в накопленном значении.
Поэтому, когда мы рассматриваем использование хвостовой рекурсии, нам может также потребоваться использовать три параметра. Для краткого введения для хвостовой рекурсивной функции требуется три параметра, поэтому мы перепишем ее следующим образом:
Используйте хвостовую рекурсию и сопоставление с образцом. Каждый раз, когда вы вызываете себя, присваивайте next to current, затем накапливайте значения current и next для нового следующего значения и вызывайте следующий раунд. Это очень похоже на описанный выше цикл мысли. Но он более функциональный и устраняет var.
3.2 Пример алгоритма 2-loadBalance
Требования, разработка программы, передача массива соотношений, например Array (1,3,6, всегда вызывайте эту функцию, соотношение 3 возвращаемых узлов также должно быть таким же, как соотношение переданных 1: 3: 6 в.
Я вызываю этот метод 10 000 раз в тестовой программе, и соотношение возвращаемых случайных узлов соответствует переданному соотношению.
Мышление：
Хотя это может достичь цели, код не является элегантным, и его лучше не использовать в функциональном программировании Scala. return Чтобы принудительно прервать выполнение функции и в конце, мне также нужно написать 0, чтобы вернуть значение по умолчанию.
Оптимизация хвостовой рекурсии
Большинство или почти все циклы for можно оптимизировать с помощью хвостовой рекурсии. Как можно оптимизировать приведенный выше код?
Идеи: Цикл for выше, каждое увеличение segment Индекс равен +1 один раз за цикл.Поэтому, когда мы проектируем хвостовую рекурсию, мы можем использовать один параметр для достижения той же функции, а другой параметр должен быть сгенерированным случайным числом.
Хорошо, давайте реализуем это
Мы видим, что при использовании хвостовой рекурсии код будет очень элегантным, теперь напишите тестовый класс для тестирования!
Как и выше, тест пройден! Это очень элегантно и чувствуется прелесть хвостовой рекурсии?
4. Оптимизация хвостовой рекурсии компилятором Scala
Scala оптимизирует формальную строгую хвостовую рекурсию. Для строгой хвостовой рекурсии аннотации не требуются.
@tailrec позволяет компилятору проверить, является ли функция хвостовой рекурсивной или нет, в противном случае он сообщит об ошибке
В частности, выполните анализ производительности на примере вычисления последовательности Фибоначчи выше.
Проведя вышеупомянутый тест времени и времени вызова, можно сделать вывод, что потребление производительности хвостовой рекурсии очень низкое, а скорость очень высокая.
4.1 Оптимизация компилятора хвостовой рекурсии
Когда компилятор обнаруживает, что вызов функции является хвостовым рекурсивным, он перезаписывает текущую активную запись вместо создания новой в стеке.
Компилятор scala обнаружит хвостовую рекурсию, оптимизирует ее и скомпилирует в шаблон цикла.
4.2 Ограничения рекурсии Scala Tail
К хвостовой рекурсии предъявляются строгие требования, то есть последний оператор является рекурсивным вызовом, поэтому метод записи более строг.
Последний вызов хвостовой рекурсии должен быть самим собой, а функции, которые косвенно назначают себя, не могут быть оптимизированы.
5. Резюме
[Конец статьи, добро пожаловать на перепечатку, укажите источник]