Функция является рекурсивной, когда во время обработки появляется ее повторный вызов непосредственно или косвенно, через цепочку вызовов других
функций.
Прямая (непосредственная) рекурсия — это вызов
функции внутри тела этой функции.
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
Очень часто рекурсивные функции можно заменить
нерекурсивными функциями или фрагментами. Это
производится путем использования стеков для хранения точек вызова и вспомогательных переменных.
