Рекурсия
Рекурсия (прилагательное: рекурсивный ) возникает, когда вещь определяется в терминах самой себя или своего типа. Рекурсия используется в различных дисциплинах, от лингвистики до логики . Наиболее распространенное применение рекурсии в математике и информатике , где определяемая функция применяется в пределах ее собственного определения. Хотя это, по-видимому, определяет бесконечное количество экземпляров (значений функции), это часто делается таким образом, что не может возникнуть бесконечный цикл или бесконечная цепочка ссылок («рекурсия черепка»).
В математике и информатике класс объектов или методов демонстрирует рекурсивное поведение, если его можно определить двумя свойствами:
Например, ниже приведено рекурсивное определение предка человека . Один из предков:
Многие математические аксиомы основаны на рекурсивных правилах. Например, формальное определение натуральных чисел аксиомами Пеано можно описать так: «Ноль — натуральное число, и каждое натуральное число имеет последующее, которое также является натуральным числом». [1] С помощью этого базового случая и правила рекурсии можно сгенерировать множество всех натуральных чисел.
Другие рекурсивно определенные математические объекты включают факториалы , функции (например, рекуррентные отношения ), множества (например, троичное множество Кантора ) и фракталы .
Рекурсия — это процесс, через который проходит процедура, когда один из шагов процедуры включает вызов самой процедуры. Процедура, которая проходит через рекурсию, называется «рекурсивной». [2]
