На этом шаге мы рассмотрим оставшиеся обобщения факториала.
Вообще говоря, если определение функции содержит произведение, то обобщение тоже должно включать произведение, умноженное на новый параметр. Точно так же, если функция содержит сумму, то обобщение должно добавлять дополнительный параметр. Это облегчает нахождение дополнительного параметра (в предыдущем примере - 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
Вариант 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 время. Кроме того, присутствие логарифмов означает, что она работает с вещественными числами вместо целых, и поэтому её результат должен округляться до ближайшего целого числа.
На следующем шаге мы вернемся к приведению десятичного числа к другому основанию.