19. Рекурсия
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
Очень часто рекурсивные функции можно заменить нерекурсивными функциями или фрагментами. Это производится путем использования стеков для хранения точек вызова и вспомогательных переменных.
Данный текст является ознакомительным фрагментом.