Рекурсивные процедуры в Рекурсивные процедуры. Их применение в языке Пролог Prolog Учебный сайт

Рекурсивные процедуры. Их применение в языке Пролог




rene-genon-o-kabbale98-rasskaz-mihaila-lajtmana-o-ego-puti-v-kabbalu-18-rasskaz-vadima-rozina-ob-ezotericheskih.html
rene-genon-simvoli-svyashennoj-nauki-stranica-11.html
Рекурсивные процедуры. Их применение в языке Пролог
Процедура рекурсивная - процедура в программировании, в теле которой находится явное обращение к ней самой, либо через другую процедуру. Например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

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

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

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

Любую рекурсивную функцию можно заменить циклом и стеком.

Рекурсивные процедуры в Prolog

Список в Прологе является рекурсивным составным объектом. Он состоит из двух частей - головы списка, которым является первый элемент, и хвоста - списка, который включает все следующие элементы.

Хвост списка всегда есть список; голова списка есть элемент:

голова списка [a, b, c] есть a

хвост списка [a, b, c] есть [b, c]

Если многократно отнимать первый элемент от хвоста списка, мы получим в конечном итоге пустой список ([ ]). Пустой список не может быть разбит на голову и хвост.

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

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



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

mpedagog.ru