Хвостовая рекурсия - Упоминания в других статьях


всего найдено упоминаний этой статьи: 7
информация о статьеПродолжение
Продолжение (англ. continuation) представляет состояние программы в определённый момент, которое может быть сохранено и использовано для перехода в это состояние. Продолжения содержат всю информацию, чтобы продолжить выполнения программы с определённой точки. Состояние глобальных переменных обычно не сохраняется, однако для функциональных языков это несущественно (выборочное сохранение/восстановление значений глобальных объектов в Scheme достигается отдельным механизмом dynamic-wind). Продолжения похожи на goto Бейсика или setjmp/longjmp Си, так как также позволяют перейти в любое место программы. Но продолжения, в отличие от goto, позволяют перейти только в участок программы с определённым состоянием, которое должно быть сохранено заранее, в то время, как goto позволяет перейти в участок программы с неинициализированными переменными. Для функциональных языков продолжением также называют функцию, передаваемую в качестве аргумента другой функции, и используемую для гибкого развития хода вычислений. Поскольку продолжение, раз использовано, не возвращает управления, такой стиль применим лишь в языках с оптимизацией хвостовой рекурсии (Scheme, ML, Haskell).

информация о статьеФункциональное программирование
В функциональных языках цикл обычно реализуется в виде рекурсии. Строго говоря, в функциональной парадигме программирования нет такого понятия как цикл. Рекурсивные функции вызывают сами себя, позволяя операции выполняться снова и снова. Для использования рекурсии может потребоваться большой стек, но этого можно избежать в случае хвостовой рекурсии. Хвостовая рекурсия может быть распознана и оптимизирована компилятором в код, получаемый после компиляции аналогичной итерации в императивном языке программирования. Стандарты языка Scheme требуют распознавать и оптимизировать хвостовую рекурсию. Оптимизировать хвостовую рекурсию можно путём преобразования программы в стиле использования продолжений при её компиляции, как один из способов.

информация о статьеБинарный алгоритм нахождения НОД
Так как алгоритм является Хвостовой рекурсией, то рекурсию можно заменить итерацией.

информация о статьеРекурсия
Впрочем, имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивают выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. К сожалению, далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Scheme (диалект языка Lisp), описание которого содержит все необходимые сведения.

информация о статьеC--
Работа над C-- началась в конце 1990-х. Поскольку написание кодогенератора само по себе является довольно сложной задачей, а бек-енды, которые были доступны исследователям тех годов, были сложными и плохо документироваными, было создано несколько проектов компиляторов, которые генерировали код на C (например, был создан компилятор языка Modula-3). Однако, язык C является плохим выбором для функциональных языков программирования: в нём нет поддержки хвостовой рекурсии, сборки мусора и эффективной обработки исключительных ситуаций. C-- является более простой альтернативой языку C, в котором присутствует поддержка всех этих возможностей. Самой инновационной особенностью в нём является интерфейс для времени исполнения, который позволяет создавать переносимые сборщики мусора, системы поддержки исключений и другие свойства, которые будуть работать с любым компилятором C--.

информация о статьеМодные слова

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


всего найдено цитат на эту статью 7
Проект wiki-linki.ru основан на данных Wikipedia, доступной в соответствии с GNU Free Documentation License.