Рекурсия
Материал из Википедии — свободной энциклопедии
Реку́рсия — метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса.
Другими словами, рекурсия — частичное определение объекта через себя, определение объекта с использованием ранее определённых. Рекурсия используется, когда можно выделить самоподобие задачи.
Определение в логике, использующее рекурсию, называется индуктивным (см., например, Натуральное число).
Содержание |
[править] Примеры
- Алгоритм Жордана—Гаусса для решения Системы линейных алгебраических уравнений является рекурсивным.
- Факториал целого неотрицательного числа n обозначается n! и определяется как
при n > 0 и n! = 1 при n = 0
- Числа Фибоначчи определяются с помощью рекуррентного соотношения:
- Первое и второе числа Фибоначчи равны 1
- Для n > 2, n − e число Фибоначчи равно сумме (n − 1)-го и (n − 2)-го чисел Фибоначчи
- Практически все геометрические фракталы задаются в форме бесконечной рекурсии. (например, треугольник Серпинского).
- Задача «Ханойские башни». Её содержательная постановка такова:
- В одном из буддийских монастырей монахи уже тысячу лет занимаются перекладыванием колец. Они располагают тремя пирамидами, на которых надеты кольца разных размеров. В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на вторую, выполняя единственное условие — кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света.
- Рекурсивный вариант решения задачи можно описать так:
Алгоритм по передвижению башни, алгоритм передвинет нужное количество дисков из пирамиды «источник» на пирамиду «задание» используя «запасную» пирамиду.
Если число дисков равно одному, тогда:
- Передвиньте диск из источника в задание
В противном случае:
- Рекурсивно передвиньте все диски кроме одного из источника в запас, используя задание как запас
- Передвиньте оставшийся диск из источника в задание
- Передвиньте все диски из запаса в задание используя источник как запас
[править] Рекурсия в программировании
[править] Функции
В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.
Мощь рекурсивного определения объекта в том, что такое конечное определение способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы.
Имеется специальный тип рекурсии, называемый «хвостовой рекурсией». Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), выполняют хвостовую рекурсию в ограниченном объёме памяти при помощи итераций.
Следует избегать избыточной глубины рекурсии, так как это может вызвать переполнение стека вызовов.
- См. также Примеры реализации функции факториал
[править] Данные
Описание типа данных может содержать ссылку на саму себя. Подобные структуры используются при описании списков и графов. Пример описания списка (C++):
class element_of_list; /* необходимо по правилам C++ */ class element_of_list { element_of_list *next; /* ссылка на следующий элемент того же типа */ int data; /* некие данные */ };
Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.
[править] Рекурсия в физике
Классическим примером бесконечной рекурсии являются два поставленные друг напротив друга зеркала: в них образуются два коридора из затухающих отражений зеркал.
Другим примером бесконечной рекурсии является эффект самовозбуждения (положительной обратной связи) у электронных схем усиления, когда сигнал с выхода попадает на вход, усиливается, снова попадает на вход схемы и снова усиливается. Усилители, для которых такой режим работы является штатным, называются автогенераторы.
[править] Рекурсия в лингвистике
Способность языка порождать вложенные предложения и конструкции. Базовое предложение кошка съела мышь может быть за счет рекурсии расширено как Ваня догадался, что кошка съела мышь, далее как Катя знает, что Ваня догадался, что кошка съела мышь и так далее. Рекурсия считается одной из лингвистических универсалий, то есть свойственна любому естественному языку (хотя в последнее время активно обсуждается возможное отсутствие рекурсии в одном из языков Амазонии — пираха, которое отмечает лингвист Д. Эверетт).
[править] Цитаты
Итерация от человека. Рекурсия — от Бога. — Л. Питер Дойч[1]
[править] Юмор
Большая часть всех шуток о рекурсии касается бесконечной рекурсии, в которой нет условия выхода. Известное высказывание: Чтобы понять рекурсию, нужно сначала понять рекурсию. Весьма популярна шутка о рекурсии, напоминающая словарную статью:
- рекурсия
- см. рекурсия
Несколько рассказов Станислава Лема посвящены (возможным) казусам при бесконечной рекурсии:
- Рассказ про Йона Тихого «Путешествие четырнадцатое» из «Звёздных дневников Ийона Тихого», в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки».
- Рассказ о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей).
Русская народная сказка-песня «У попа была собака…» являет пример рекурсии:
У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
- "У попа была собака, он её любил,
- Она съела кусок мяса, он её убил,
- В землю закопал,
- Надпись написал:
- "У попа была собака, он её любил,
- Она съела кусок мяса, он её убил,
- В землю закопал,
- Надпись написал:
- …
[править] См. также
- Индукция
- Математическая индукция
- Корекурсия
- Рекуррентная последовательность (возвратная последовательность)
[править] Ссылки
- ↑ * Дональд Кнут Искусство программирования, том 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
 |
Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её. |
