Рекурсивный и итеративный процесс

В математике и программировании существует понятие рекурсии — когда что-то состоит из себя же. Рекурсия делится на конечную и бесконечную, первая — хорошая, вторая — интересная.

Хороший пример конечной рекурсии — матрёшка: из самой большой появляется матрёшка поменьше, а из неё еще поменьше, пока не дойдёт до самой маленькой. Она нам показывает, что дальше разбирать не получится, пора собирать назад, это называется условием выхода из рекурсии.

Любая рекурсия из жизни имеет условие выхода

Дело в том, что в жизни бесконечной рекурсии нет, все примеры это выдуманные вещи и явления.
Пример бесконечной рекурсии — фрактальные фигуры, они состоят сами из себя.

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

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

Глубина рекурсии зависит от транслятора

Рекурсия и инструкции

Код состоит из выражений и инструкций, про это была статья. Большинство блоков кода строятся из групп инструкций, по-другому их называют процессами.
В коде, рекурсия описывается двумя способами: рекурсивным процессом и итеративным процессом.

Рекурсивный процесс

Запоминает все данные, пока не закончит цепочку вызовов. Интерпретатор сначала доходит до края рекурсии и только потом начинает вычисления от самого последнего вызова. Этот способ занимает много памяти, потому что при каждой прокрутке он запоминает новые данные в добавку к старым.
Это как голодать весь день и плотно поесть вечером — не очень полезно, но иногда приходится.

Вот так выглядит рекурсивный подсчёт факториала

Итеративный процесс

Считает все данные, которые можно посчитать на текущей итерации и передаёт их в следующий вызов.
А это как делать 7-8 мелких перекусов в течение дня.

Благодаря выражению num * acc в пятой строке итеративный процесс не разрастается так, как рекурсивный, потому что значение передаётся в следующую итерацию.


Со следующей статьи начинаем делать себе телеграм-бота, напишем приветствие и простой сценарий диалога.

Поделиться
Отправить
Запинить
Популярное