На этом шаге мы рассмотрим линейный тип рекурсии.

Линейный тип рекурсии появляется, когда методы вызывают себя только однажды. Есть два типа линейно-рекурсивных методов, однако мы будем применять термин "линейная рекурсия", когда имеем дело с методами, которые так или иначе обрабатывают результат рекурсивного вызова до выдачи или возврата своего собственного результата. Например, функция вычисления факториала в (1.3) относится к этой категории, так как выполняет только один рекурсивный вызов, а результат подзадачи умножается на n, чтобы получить результат функции. Функции в (1.5), (1.9) и (1.10) тоже являются очевидными примерами линейной рекурсии. Следующая функция представляет собой другой пример функции Фибоначчи:

         1,                         если n = 1 или n = 2
f(n) =                                                  (1.14)
         ⌊ Φ ⋅ f(n - 1) + 1 / 2 ⌋,  если n > 2

где Φ = (1 + √5)/2 ≈ 1.618 - константа, известная под названием "золотое сечение", а ⌊ и ⌋ обозначают нижнюю границу. В этом случае F(n) = f(n) - n-е число Фибоначчи. Такой тип линейно-рекурсивных алгоритмов будет подробно рассмотрен позже.

На следующем шаге мы рассмотрим хвостовую рекурсию.

Предыдущий шаг Содержание Следующий шаг