- У попа была собака
-
Реку́рсия — метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса, ссылающегося прямо или косвенно на эти базовые случаи.
Другими словами, рекурсия — способ общего определения объекта или действия через себя, с использованием ранее заданных частных определений. Рекурсия используется, когда можно выделить самоподобие задачи.
Определение в логике, использующее рекурсию, называется индуктивным (см., например, Натуральное число).
Содержание
Примеры
- Метод Гаусса — Жордана для решения Системы линейных алгебраических уравнений является рекурсивным.
- Факториал целого неотрицательного числа n обозначается n! и определяется как
- при n > 0 и n! = 1 при n = 0
- Числа Фибоначчи определяются с помощью рекуррентного соотношения:
- Первое и второе числа Фибоначчи равны 1
- Для n > 2, n − e число Фибоначчи равно сумме (n − 1)-го и (n − 2)-го чисел Фибоначчи
- Практически все геометрические фракталы задаются в форме бесконечной рекурсии. (например, треугольник Серпинского).
- Задача «Ханойские башни». Её содержательная постановка такова:
- В одном из буддийских монастырей монахи уже тысячу лет занимаются перекладыванием колец. Они располагают тремя пирамидами, на которых надеты кольца разных размеров. В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие — кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света.
- Рекурсивный вариант решения задачи можно описать так:
Алгоритм по передвижению башни, алгоритм передвинет нужное количество дисков из пирамиды «источник» на пирамиду «задание» используя «запасную» пирамиду.
Если число дисков равно одному, тогда:
- Передвиньте диск из источника в задание
В противном случае:
- Рекурсивно передвиньте все диски кроме одного из источника в запас, используя задание как запас
- Передвиньте оставшийся диск из источника в задание
- Передвиньте все диски из запаса в задание используя источник как запас
Рекурсия в программировании
Функции
В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Мощь рекурсивного определения объекта в том, что такое конечное определение способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Реализация рекурсивных вызовов функций в практически применяемых языках и средах программирования, как правило, опирается на механизм стека вызовов — адрес возврата и локальные переменные функции записываются в стек, благодаря чему каждый следующий рекурсивный вызов этой функции пользуется своим набором локальных переменных и за этот счёт работает корректно. Оборотной стороной этого довольно простого по структуре механизма является то, что рекурсивные вызовы не бесплатны — на каждый рекурсивный вызов требуется некоторое количество оперативной памяти компьютера, и при чрезмерно большой глубине рекурсии может наступить переполнение стека вызовов. Вследствие этого обычно рекомендуется избегать рекурсивных программ, которые приводят (или в некоторых условиях могут приводить) к слишком большой глубине рекурсии.
Впрочем, имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивают выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти. К сожалению, далеко не всегда стандарты языков программирования чётко определяют, каким именно условиям должна удовлетворять рекурсивная функция, чтобы транслятор гарантированно преобразовал её в итерацию. Одно из редких исключений — язык Lisp), описание которого содержит все необходимые сведения.
- См. также Примеры реализации функции факториал
Данные
Описание типа данных может содержать ссылку на саму себя. Подобные структуры используются при описании списков и графов. Пример описания списка (C++):
class element_of_list { element_of_list *next; /* ссылка на следующий элемент того же типа */ int data; /* некие данные */ };
Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.
Рекурсия в физике
Классическим примером бесконечной рекурсии являются два поставленные друг напротив друга зеркала: в них образуются два коридора из затухающих отражений зеркал.
Другим примером бесконечной рекурсии является эффект самовозбуждения (положительной обратной связи) у электронных схем усиления, когда сигнал с выхода попадает на вход, усиливается, снова попадает на вход схемы и снова усиливается. Усилители, для которых такой режим работы является штатным, называются автогенераторы.
Рекурсия в лингвистике
Способность языка порождать вложенные предложения и конструкции. Базовое предложение кошка съела мышь может быть за счет рекурсии расширено как Ваня догадался, что кошка съела мышь, далее как Катя знает, что Ваня догадался, что кошка съела мышь и так далее. Рекурсия считается одной из лингвистических универсалий, то есть свойственна любому естественному языку (хотя в последнее время активно обсуждается возможное отсутствие рекурсии в одном из языков Амазонии — пираха, которое отмечает лингвист Д. Эверетт). О рекурсии в лингвистике, ее разновидностях и наиболее характерных проявлениях в русском языке описано в статье Е.А.Лодатко "Рекурсивные лингвистические структуры" (см.: Рекурсивные лингвистические структуры)
Цитаты
Юмор
Большая часть всех шуток о рекурсии касается бесконечной рекурсии, в которой нет условия выхода. Известные высказывания: 'Чтобы понять рекурсию, нужно сначала понять рекурсию', 'Чтобы что-то сделать, надо что-то сделать', 'Для приготовления салата необходимы: огурцы, помидоры, салат'. Весьма популярна шутка о рекурсии, напоминающая словарную статью:
- рекурсия
- см. рекурсия
Несколько рассказов Станислава Лема посвящены (возможным) казусам при бесконечной рекурсии:
- Рассказ про Йона Тихого «Путешествие четырнадцатое» из «Звёздных дневников Ийона Тихого», в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки».
- Рассказ о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей).
Русская народная сказка-песня «У попа была собака…» являет пример рекурсии:
У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:- "У попа была собака, он её любил,
- Она съела кусок мяса, он её убил,
- В землю закопал,
- Надпись написал:
- "У попа была собака, он её любил,
- Она съела кусок мяса, он её убил,
- В землю закопал,
- Надпись написал:
-
-
- …
-
См. также
- Индукция
- Математическая индукция
- Корекурсия
- Рекуррентная последовательность (возвратная последовательность)
Ссылки
- ↑ * Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
Wikimedia Foundation. 2010.