Биология

Биология - Рекурсия - Примеры

Треугольник Серпинского

• Метод Гаусса — Жордана для решения систем линейных алгебраических уравнений является рекурсивным.
• Факториал целого неотрицательного числа n определяется как

  при n > 0 и n! = 1 при n = 0

• Числа Фибоначчи определяются с помощью рекуррентного соотношения:

  Первое и второе числа Фибоначчи равны 1

  Для n > 2, n − e число Фибоначчи равно сумме -го и -го чисел Фибоначчи

• Практически все геометрические фракталы задаются в форме бесконечной рекурсии.
• Рекурсивные акронимы: GNU, PHP и т. д.

Рекурсия в программировании

Функции

В программировании рекурсия — вызов функции из неё же самой, непосредственно или через другие функции, например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии.

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

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

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

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

• См. также примеры реализации функции факториал

Данные

Описание типа данных может содержать ссылку на саму себя. Подобные структуры используются при описании списков и графов. Пример описания списка:

 class element_of_list
 {
   element_of_list *next; /* ссылка на следующий элемент того же типа */
   int data; /* некие данные */
 };

Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.