На этом шаге мы рассмотрим приемлемые обобщения для факториала.

Первый шаг состоит в выборе конкретного обобщения, с которым мы будем работать. Из нескольких вариантов обобщения функции факториала сначала разберём g(n, p) = p * n!, так как он приводит к простому хвостовому рекурсивному алгоритму. Этот выбор объясняется ещё и тем, что другие обобщения обычно приводят к неэффективным и сложным вложенным рекурсивным функциям.

Для построения рекурсивного алгоритма для g(n, p) можно действовать так же, как в предыдущих шагах. Размер задачи - n. Поэтому начальное условие выполняется при n = 0, когда функция просто возвращает p (то есть g(0, p) = p). Для рекурсивного условия можно попытаться уменьшить n на 1, что привело бы к следующей рекурсивной схеме:

Однако такая декомпозиция приводит не к хвостовому рекурсивному алгоритму, а к линейному, поскольку результат подзадачи здесь должен умножаться на n. В этом случае предыдущая схема бесполезна, потому что она не учитывает тот факт, что цель состоит в разработке хвостового рекурсивного метода, когда результат подзадачи должен совпадать с результатом исходной задачи. Поскольку g(n, p) ≠ g(n - 1, p), то прежде всего должен быть изменён способ декомпозиции. Если мы хотим уменьшить размер задачи на 1, то должны использовать другое выражение для второго параметра. Например, g(n, p) = g(n - 1, q), где q - фиктивная переменная, представляющая собой выражение от входных параметров n и р. Теперь наша цель - определить q, которую можно найти, построив другую, но похожую схему:

Во-первых, следует обратить внимание, что все элементы схемы равны: g(n, р) = р * n! - определение обобщённой функции, тогда как g(n, р) = g(n - 1, q) должно быть хвостовым рекурсивным правилом. Применение определения g(n - 1, q) естественно приводит к g(n - 1, q) = q * (n - 1)!. Наконец, формулы в правой части схемы тоже должны быть равными и могут использоваться для получения q. В данном случае мы имеем:

  р * n! = q * (n - 1)!,

откуда следует, что q = р * n. В итоге функция определяется следующим образом:

              p,                если n = 0,
    g(n, p) = 
              g(n - 1, p * n)), если n > 0

что соответствует методу factorial_tail(n, p) в примере 11.4 (а f(n) = g(n, 1) становится функцией-оболочкой). В этом случае параметр р - это результат использования обобщённой функции, а не переменная-накопитель, как в итерационном алгоритме.

На следующем шаге мы рассмотрим неприемлемые обобщения.

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