Что такое хвостовая рекурсия
F# Хвостовая рекурсия. Подводные грабли. Часть 1
Винни Пух: Ой, что это случилось с твоим хвостом?
Иа: А что с ним могло случится?
Винни Пух: Его нет.
Иа: Ты не ошибся?
Винни Пух: Хвост или есть или нет совсем! Тут нельзя ошибиться.
Иа: А что же тогда там есть?
Винни Пух: Ничего!
Все дело было в хвостовой рекурсии, вернее, как оказалось в ее отсутствии в неожиданных местах.
Хвостовая рекурсия
Рекурсия, это наверно один из самых важных инструментов в арсенале функционального программирования. А так как при рекурсивных вызовах используется стек, который, как известно, не безграничен, то может показаться, что применение рекурсии ограничено, и глубина рекурсии конечна.
Однако, все не так мрачно, практически все компиляторы функциональных языков, имеют такую полезную штуку как оптимизация хвостовой рекурсии, с помощью которой можно использовать рекурсию без использования стека, что в свою очередь снимает ограничение на вложенность рекурсии.
Хвостовая рекурсия это частный случай рекурсии, когда рекурсивный вызов может быть заменен итерацией. С одной стороны на совести программиста остается написание логики в «хвостовом» стиле, с другой стороны компилятор тоже должен «обнаружить» хвостовую рекурсию и раскрутить рекурсию в итерацию.
Давайте рассмотрим первый такой случай и сформулируем правило, с помощью которого можно избежать «неприятностей».
Давайте, для начала возьмем простую функцию, которая суммирует числа все числа от одного до N:
Все хорошо, за исключением одной момента. Если мы попробуем посчитать сумму хотя бы для 100000, то получим в лоб StackOverflowException. Т.е. у нас банально не хватило стека для вычислений:
Ответ на эту проблему, использование аккумулятора, как аргумента рекурсивной функции:
Мы переписали нашу функцию таким образом, что стек ей оказывается не нужен, вместо того чтобы возвращаться назад для суммирования, мы пробрасываем аккумулятор в качестве аргумента.
Проиллюстрировать порядок вычисления (для аргумента 5) можно так. Без хвостовой рекурсии:
С хвостовой рекурсией:
Новая функция уже может переварить сколь угодно большое число (пока хватит разрядности int64).
Теперь, давайте немного напишем более обобщенную функцию, которая суммирует не сами числа, а результат некоторой заданной функции от текущего числа.
В новой версии у нас появился еще один параметр – функция, результат вычисления которой нужно суммировать. Вот вариант, который суммирует сами числа:
А вот, который суммирует квадраты:
Пока все хорошо. Но есть небольшой нюанс, функция которая передается, может «кинуть» исключение. Вот пример:
Проблема
При значении i = 999, у нас возникает деление на ноль. Предположим, что мы хотим при исключении, не аварийно завершать вычисление, а просто игнорировать проблемный элемент. Нам понадобится обработка исключения. Само собой напрашивается вполне логичное и ожидаемое решение:
Результат получили, исключения отловили, вроде все нормально. Теперь пробуем скормить более серьезное число:
Упс… В чем же дело? На первый взгляд у нас функция с хвостовой рекурсией, почему вдруг закончился стек?
Как можно догадаться, проблема в конструкции try … with. Дело в том, что если рекурсивный вызов выполняется в блоке try, то у хвостовой рекурсии «отваливается» хвост, и она становится обычной рекурсией. Почему? Потому что в любом из последующих рекурсивных вызовов loop, теоретически может выпасть исключение, а т.к. нам надо его будет обработать, то нужно запомнить в стеке место, куда нужно вернуться при «выпадении» исключения.
Решение
Какой из такой неприятной ситуации выход? Очень простой, не нужно оборачивать рекурсивный вызов блоком try… with, ведь исключение мы ожидаем только при вызове «внешней» функции f, значит оборачивать нужно только этот вызов:
Вуаля! Стека на этот раз хватило, вернее он остался не тронутый.
Итак, правило: никогда не помещайте хвостовой вызов в блок try… with.
Во второй серии будут шокирующие разоблачения касающиеся хвостовой рекурсии для async < … >и MailboxProcessor.
Хвостовая рекурсия в C++ с использованием 64-битных переменных — Часть 1
В этот раз я хочу поделиться с вами одной проблемой, с которой столкнулся, когда решил сравнить итерационные и рекурсивные функции в C++. Между рекурсией и итерацией есть несколько отличий: о них подробно рассказано в этой стать. В языках общего назначения вроде Java, C или Python рекурсия довольно затратна по сравнению с итерацией из-за необходимости каждый раз выделять новый стековый фрэйм. В C/C++ эти затраты можно легко устранить, указав оптимизирующему компилятору использовать хвостовую рекурсию, при которой определенные типы рекурсии (а точнее, определенные виды хвостовых вызовов) преобразуются в команды безусловного перехода. Для осуществления такого преобразования необходимо, чтобы самым последним действием функции перед возвратом значения был вызов еще одной функции (в данном случае себя самой). При таком сценарии безусловный переход к началу второй подпрограммы безопасен. Главный недостаток рекурсивных алгоритмов в императивных языках заключается в том, что в них не всегда возможно иметь хвостовые вызовы, т.е. выделение места для адреса функции (и связанных с ней переменных, например, структур) на стеке при каждом вызове. При слишком большой глубине рекурсии это может привести к переполнению стека из-за ограничения на его максимальный размер, который обычно на порядки меньше объема оперативной памяти.
В качестве теста для изучения хвостовой рекурсии я написал в Visual Studio простую функцию Фибоначчи на C++. Давайте посмотрим, как она работает:
Чтобы перед возвратом значения получился хвостовой вызов, функция fib_tail в качестве последнего действия вызывает саму себя. Давайте теперь взглянем на сгенерированный ассемблерный код. Для этого я скомпилировал программу в релиз-режиме с использованием ключа оптимизации /O2. Вот как выглядит этот код:
Есть! Обратите внимание на последнюю строку: в ней вместо инструкции CALL используется JMP. В данном случае хвостовая рекурсия сработала, и у нашей функции не возникнет никаких проблем с переполнением стека, поскольку на уровне ассемблера она превратилась в итерационную функцию.
Этого мне было мало, и я решил поэкспериментировать с производительностью, увеличив входную переменную n. Затем я изменил тип переменных, используемых в функции, с int на unsigned long long. Запустив программу повторно, я внезапно получил переполнение стека! Вот как выглядит этот вариант нашей функции:
Давайте снова взглянем на сгенерированный ассемблерный код:
Как я и ожидал, хвостовой рекурсии тут не оказалось! Теперь вместо ожидаемой JMP используется CALL. Между тем, единственное различие между двумя вариантами нашей функции заключается в том, что во втором случае я использовал 64-битную переменную вместо 32-битной. В связи с чем возникает вопрос: почему компилятор не задействует хвостовую рекурсию при использовании 64-битных переменных?
Я решил скомпилировать программу в 64-битном режиме и посмотреть, как она себя поведет. Сгенерированный ассемблерный код:
Здесь хвостовая рекурсия снова появилась! Благодаря 64-битным регистрам (rax, r8, rcx, rdx) вызывающая и вызываемая функции имеют общий стек, а вызываемая функция возвращает результат непосредственно в точку вызова внутри вызывающей функции.
Я задал свой вопрос на сайте StackOverflow – похоже, что проблема в самом компиляторе Microsoft C++. Автор одного из комментариев сообщил, что в остальных C++-компиляторах эта проблема не наблюдается, но я должен убедиться в этом сам.
Я выложил пример кода на GitHub – можете скопировать его и попробовать запустить у себя. На Reddit и Stackoverflow мне также сказали, что в издании VS2013 Community Edition описанная проблема не возникает. Я попробовал поработать в VS2013 Ultimate, но столкнулся с ней и там. В течение ближайших дней попробую потестировать код под GCC и сравню результаты.
См. проект Example на GitHub.
Надеюсь, что мое расследование окажется полезным и для вас, если вам вдруг тоже доведется разбираться, почему в определенных случаях компилятор не реализует хвостовую рекурсию.
Хвостовая рекурсия
Хвостовая рекурсия — специальный случай рекурсии, при котором рекурсивный вызов функцией самой себя является её последней операцией. [1] Подобный вид рекурсии примечателен тем, что может быть легко заменён на итерацию, что реализовано во многих оптимизирующих компиляторах.
Содержание
Описание
Когда происходит вызов функции, компьютер должен запомнить место, из которого функция была вызвана (адрес возврата), чтобы после её окончания вернуться и продолжить выполнение программы. Обычно адрес возврата сохраняется в стеке. Иногда последнее действие функции после завершения всех других операций, это просто вызов функции, возможно самой себя, и возвращение результата. В этом случае нет необходимости запоминать адрес возврата, вновь вызываемая функция будет возвращать результат непосредственно к месту вызова первоначальной функции.
Применение
Хвостовая рекурсия часто применяется в программах на функциональных языках программирования. Многие вычисления на таких языках естественно выражать в виде рекурсивных функций, а возможность автоматической замены транслятором хвостовой рекурсии на итерацию означает, что по вычислительной эффективности она равна эквивалентному коду, записанному в итеративном виде.
Создатели функционального языка Scheme, одного из диалектов Lisp, оценили важность хвостовой рекурсии настолько, что в спецификации языка предписали каждому транслятору этого языка в обязательном порядке реализовывать оптимизацию хвостовой рекурсии. [2]
Примеры
Пример рекурсивной функции для вычисления факториала, использующей хвостовую рекурсию на языках программирования Scheme и C:
Контрпример
Стоит отметить, что другой, более естественный рекурсивный способ вычисления факториала, приведённый ниже, не является хвостово-рекурсивным, так как в каждом вызове функции после рекурсивного вызова производятся дополнительные операции, а именно умножение на n.
См. также
Примечания
Полезное
Смотреть что такое «Хвостовая рекурсия» в других словарях:
Переполнение стека — Эта статья о компьютерной ошибке. О сайте для программистов см. Stack Overflow. В программном обеспечении переполнение стека (англ. stack overflow) возникает, когда в стеке вызовов хранится больше информации, чем он… … Википедия
ECMAScript — Класс языка: мультипарадигменный: объектно ориентированное, обобщённое, функциональное, императивное, аспектно ориентированное, событийно ориентированное, прототипное программирование Появился в: 1995 Автор(ы) … Википедия
Функциональное программирование — Парадигмы программирования Агентно ориентированная Компонентно ориентированная Конкатенативная Декларативная (контрастирует с Императивной) Ограничениями Функциональная Потоком данных Таблично ориентированная (электронные таблицы) Реактивная … Википедия
Парадигма — (Paradigm) Определение парадигмы, история возникновения парадигмы Информация об определении парадигмы, история возникновения парадигмы Содержание Содержание История возникновения Частные случаи (лингвистика) Управленческая парадигма Парадигма… … Энциклопедия инвестора
Scheme — Семантика: функциональный Тип исполнения: интерп … Википедия
Nemerle — Семантика: мультипарадигменный, объектно ориентированный, функциональный, императивный Тип исполнения: компилируемый Появился в: 0.9.3 16 мая … Википедия
Модные слова — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете … Википедия
Красно-чёрное дерево — Тип дерево поиска Изобретено в 1972 году Изобретено Рудольф Байер Временная сложность в О символике В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(log n) O(log n) Вставка O(log n) O(log n) Удаление O(log n) O(log n) Красно чёрное… … Википедия
Scheme (язык программирования) — Scheme Семантика: функциональный Тип исполнения: интерпретатор или компилятор Появился в: 1970 г. Автор(ы): Гай Стил и Джеральд Сассмен Типизация данных … Википедия
Зона кода
Эту статью я написал несколько лет назад для другого сайта, но она так и не была опубликована. Тогда 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 оптимизирует хвостовую рекурсию.
Что такое хвостовая рекурсия?
начиная изучать 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++ могут все равно ее оптимизировать).