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

Вообще говоря, если определение функции содержит произведение, то обобщение тоже должно включать произведение, умноженное на новый параметр. Точно так же, если функция содержит сумму, то обобщение должно добавлять дополнительный параметр. Это облегчает нахождение дополнительного параметра (в предыдущем примере - q) в подзадаче.

Но не все обобщения приводят к хвостовым рекурсивным алгоритмам. Например, рассмотрим g(n, р) = р + n!, использующую вместо произведения сумму. Во-первых, начальное условие было бы g(0, р) = р + 0! = р + 1. Для рекурсивного условия мы можем сформировать следующую диаграмму:

В этом случае определить q сложнее. Начав с q + (n - 1)! = p + n!, мы получим:

  q = p + n! - (n - 1)! = p + (n - 1) * (n - 1)! = p + (n - 1) * g(n - 1, 0),

где последнее равенство следует из определения обобщения. Таким образом, функцию можно определить как

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

что является примером вложенной рекурсии. Хотя алгоритм - правильный, он не только более сложный, но ещё и менее эффективный. Его дерево рекурсии является полным двоичным деревом, из чего следует, что его временная сложность порядка Θ(2ⁿ).

Вариант g(n, p) = (n!)^p еще более затруднителен. Чтобы решить уравнение ((n - 1)!)^q = (n!)^p, нужно сначала прологарифмировать (основание логарифма не имеет значения) обе его части. Это приводит к q log((n - 1)!) = p log(n!). Таким образом, мы имеем:

  q = p log(n!) / log((n - 1)!) = p (log(n) + log((n - 1)!)) / log((n - 1)!) =
    = p (log(n) / log((n - 1)!) + 1) = p (log(n) / log(g(n - 1, 1)) + 1).

Это выражение верно только для n > 2 (обратите внимание, что невозможно получить q для (1!)^q = (2!)^p). Таким образом, для вывода правильной функции нам потребуется несколько начальных условий, а саму функцию можно определить следующим образом:

              1,                                           если n ≤ 0
    g(n, p) = 2p,                                          если n = 2
              g(n - 1, p *(log(n) / log(g(n - 1, 1)) + 1), если n > 2

Как видим, она тоже содержит вложенную рекурсию. Как и (11.5), она выполняется за экспоненциальное от n время. Кроме того, присутствие логарифмов означает, что она работает с вещественными числами вместо целых, и поэтому её результат должен округляться до ближайшего целого числа.

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

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