Delphi. Рекурсия по простому

Данная статья посвящена рекурсии. Понравились картинки из сети на тему рекурсии)))

1

3


Элементарно, ребята!

Если по простому, то рекурсия функции / процедуры — это вызов самой себя, в своём же теле. Например так…

Но если нет цели — подвесить систему — лучше так не делать. Процедура вызывает саму себя бесконечно и ничего не происходит, кроме этого, отсутствует так называемая терминальная ветвь рекурсии. Даже если убрать это «удовольствие» в отдельный поток — ресурсы системы будут расходоваться. Нужен какой-то выход из рекурсии. Самое простое — дописать счетчик, например так…

В Википедии очень хорошо и подробно написано на эту тему. Цитирую

Структурно рекурсивная функция / процедура на верхнем уровне всегда представляет собой команду ветвления (выбор одной из двух или более альтернатив в зависимости от условия (условий), которое в данном случае уместно назвать «условием прекращения рекурсии»), имеющей две или более альтернативные ветви, из которых хотя бы одна является рекурсивной и хотя бы одна — терминальной. Рекурсивная ветвь выполняется, когда условие прекращения рекурсии ложно, и содержит хотя бы один рекурсивный вызов — прямой или опосредованный вызов функцией самой себя. Терминальная ветвь выполняется, когда условие прекращения рекурсии истинно;

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


Красим забор рекурсивно!

В одной из книг по алгоритмам, прочитал про покраску забора — можно покрасить его слева направо как единое целое, а можно разделить на 4 части и в определенной последовательности красить эти 4 части.

В псевдокоде это можно представить так

Процедура Покрасить забор (длина забора)

Начало

Если забор покрашен, то выйти из процедуры;

Процедура Покрасить забор (1 / 4 длины забора);

Перейти на следующую четверть;

Конец


Куда же без факториала?

Какой источник не возьми по рекурсиям — везде факториал ))). Не будем нарушать эту славную традицию 🙂

Но для начала вспомним что такое факториал, опять же из Википедии

Факториал это произведение всех натуральных чисел от 1 до n включительно:

4

Рекурсивная функция факториала в Delphi

Сложность алгоритма оценивается как O(N). Эту функцию можно написать и не рекурсивно, но об этом в другой статье. Ради интереса посмотрим как ведет себя факториал

5

Движемся дальше.

Основа всего сущего — числа Фибоначи!

Рекурсивное определение чисел Фибоначи может быть таким

Рекурсивная реализация на Delphi будет выглядеть таким образом

Сложность алгоритма O(N);

Числа Фибоначи встречаются во многих уголках вселенной, например, ракушки…

6

 

Рекурсия и память

Известно, что когда мы используем процедуры и функции, то переменные внутри них «живут», пока работает сама процедура или функция, но что происходит во время рекурсии? Когда мы N раз внутри одной процедуры открыли её саму же — ну логично! Все переменные N раз дублируются. Понимаете к чему я веду? Рекурсивные алгоритмы, не смотря на свою изящность — скажу по русски — «жрут» память. Что делать в таком случае? Варианта два. Первый — попробовать вынести локальные переменные в глобальные, и если это не помогло, то всё очень просто — заменить рекурсивный алгоритм на обычный.

Вот пример для факториала — переписали его в цикле, теперь память не «жрется»;

Выводы по рекурсии

-Всегда писать терминальную ветвь

-При глубокой рекурсии — выносить переменные в глобальные, либо переписать алгоритм не рекурсивно.

Вообще говоря, на мой взгляд с рекурсией код изящней, но и сложнее для восприятия, да и для памяти — нагрузка. Как говорится — если можно лучше и проще, то давайте — лучше и проще!