На этом шаге мы дадим определение этому типу рекурсии.
Второй тип линейной рекурсии называют "хвостовой рекурсией". Методы, относящиеся к этой категории, также вызывают себя лишь однажды, но рекурсивный вызов - это последнее действие в рекурсивном условии. Следовательно, оно никак не влияет на результат рекурсивного вызова. Для примера рассмотрим следующую хвостовую рекурсивную функцию:
b, если n = 1
f(n, a, b) = (1.15)
f(n - 1, a + b, a), если n > 1
Обратите внимание, что в рекурсивном условии метод просто возвращает результат рекурсивного вызова, который не входит в математическое или логическое выражение. Поэтому рекурсивное условие определяет лишь отношение между наборами параметров, для которых функция возвращает одно и то же значение. Выполняя рекурсивные вызовы, алгоритм лишь изменяет параметры, пока нет возможности получить решение из начального условия. В этом случае числа Фибоначчи F(n) могут быть получены из f(n, 1, 1). Этот тип рекурсивных алгоритмов также будет подробно рассматрен позже.
На следующем шаге мы рассмотрим множественную рекурсию.
