19. Рекурсия

We use cookies. Read the Privacy and Cookie Policy

19. Рекурсия

Функция является рекурсивной, когда во время обработки появляется ее повторный вызов непосредственно или косвенно, через цепочку вызовов других функций.

Прямая (непосредственная) рекурсия – это вызов функции внутри тела этой функции.

int a()

{…..a()…..}

Косвенная рекурсия – это рекурсия, которая осуществляет рекурсивный вызов функции через цепочку вызова других функций. Все функции, которые входят в цепочку, тоже являются рекурсивными. Рассмотрим пример:

a(){…..b()…..}

b(){…..c()…..}

c(){…..a()…..}.

Все представленные функции a, b, c считаются рекурсивными, так как в случае вызова одной из них производится вызов других и самой себя.

Последовательность вызовов процедуры tn, если m = 3, можно проиллюстрировать древовидной структурой (рис. 2). Всякий раз при вызове процедуры tn под параметры n, i, j, w определяется память и запоминается место возврата. В случае возврата из процедуры tn память, которая выделяется под параметры n, i, j, w, освобождается и становится доступной память, которая выделена под параметры n, i, j, w предыдущим вызовом, а управление передается в место возврата.

Рис. Последовательность вызовов процедуры tn

Очень часто рекурсивные функции можно заменить нерекурсивными функциями или фрагментами. Это производится путем использования стеков для хранения точек вызова и вспомогательных переменных.

Данный текст является ознакомительным фрагментом.