Статья в Энциклопедическом Фонде

Рекурсия

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

В программировании:
Рекурсия - вызов функции из неё же самой (обычно с другими значениями входных параметров), непосредственно или через другие функции (например, функция А вызывает функцию B, а функция B - функцию A). Количество вложенных вызовов функции называется глубиной рекурсии. Мощь рекурсивного определения объекта в том, что такое конечное определение способно описывать бесконечно большое число объектов. С помощью рекурсивной программы же возможно описать бесконечное вычисление, причём без явных повторений частей программы. Но рекурсивная программа не может вызывать себя бесконечно, иначе она никогда не остановится, таким образом в программе (функции) должна присутствовать еще один важный элемент - так называемое терминальное условие, то есть условие при котором программа прекращает рекурсивный процесс.

Реккурентность - это рекурсивное определение функции. Они широко распространены в математике. Возможно наиболее знакомая Вам из такого рода функций - это факториал. Факториал - это произведение натуральных чисел от единицы до какого - либо данного натурального числа. Он определяется формулой:

N!=N((N-1)!,     для N>=1 и 0! = 1.

Это напрямую соответствует нижеследующей рекурсивной программе:

function factorial( N : integer ) : integer;

begin

if N=0 then

factorial := 1

else

factorial := N * factorial(N-1);

end;

Эта программа демонстрирует основные свойства рекурсивных программ: программа вызывает сама себя (с меньшим значением аргумента), и у нее есть терминальное условие при котором она прямо вычисляет результат.

В математике:
Рассмотрим последовательность чисел   в которой каждое число является суммой двух предыдущих. Это числа Фибоначчи. История предполагает, что числа Фибоначчи были придуманы в Италии (XII -XIII вв.) одним из самых выдающихся математиков того времени. Он ускорил процесс развития физики, математики, техники и астрономии, а также выпустил три работы, самая известная называется "Liber Abaci".  Формальное их определение таково:

F(1) = 1?,F(2) = 1?,F(n) = F(n ? 2) + F(n ? 1)если?, n > 2.

Функция F(n) задана рекурсивно, то есть "через себя". База - значения функции F на аргументах 1 и 2, а шаг - формула

F(n) = F(n ? 2) + F(n ? 1).

Бесконечная рекурсия в жизни:
Эффект Droste - термин для изображения специфического вида рекурсивного изображения. Изображение включает уменьшенный собственный вариант самого себя. Этот более малый вариант после этого показывает даже более малый вариант себя, и так далее. Практически это продолжается пока разрешение изображения позволяет уменьшает размер. Термин был введен в честь Droste, голландского какао.
Классическим примером бесконечной рекурсии являются два поставленные друг напротив друга зеркала: в них образуются два коридора из затухающих отражений зеркал.

Используемые источники:
1. structur.h1.ru/recurs.htm
2. ru.wikibooks.org/wiki
3. botinok.co.il/node/29842

Энциклопедический Фонд