адача 27. Составить рекурсивную программу-функцию вычисления значений многочлена по схеме Горнера.

Решение. Пусть f(x) - многочлен с вещественными или комплексными коэффициентами и v - вектор этих коэффициентов:

                                                      (11)

                                                                                  (12)

Вычисление f(x) в точке x по схеме Горнера проводится от самых внутренних скобок и далее в соответствии с представлением:

Отсюда ясно, как записать рекурсивный и нерекурсивный варианты алгоритмов вычисления f(x). Нас интересует только первый из них. Параметрами задачи можно считать вектор v и точку a для вычисления f(a). Тривиальный случай – многочлен нулевой степени: . Декомпозиция получается из указанной выше расстановки скобок в записи f(x). Соответствующая программа-функция выглядит, например, так:

Контрольный пример:

Замечание. Параметр n – это константа, равная степени многочлена. По вектору v она определяется однозначно. Однако в каждом рекурсивном вызове проводится перевычисление n. Избежать лишней вычислительной работы в подобных ситуациях можно двумя способами: или определять такие константы глобально (до текста программы-функции), или передавать их значения через дополнительные аргументы функции. В последнем случае программа horner() могла бы выглядеть так:

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

 Плодотворная идея специальной расстановки скобок для эффективного вычисления значения многочлена в точке может работать и в иных ситуациях. Остановимся на одной из них.

адача 28. Составить рекурсивную программу-функцию вычисления суммы S факториалов целых чисел от 0 до n включительно: .

Решение. Поскольку

,

то искомая функция sumfа() могла бы выглядеть, например, так:

где S - вспомогательный параметр, в котором формируется значение требуемой суммы факториалов, а k - переменная, управляющая рекурсивными вызовами. Начальные значения S и k при обращении к sumfa() должны быть равны соответственно единице и n.

 Контрольные примеры:

sumfa(4,1)=34,

sumfa(40,1)® 836850334330315506193242641144055892504420940314.

Вычисления факториальных сумм вида проводится по аналогичной рекурсивной схеме, исходящей из представления:

Если задавать коэффициенты a_k (k = 0,1,...,n) факториальной суммы в виде вектора a = (a₀   a₁  ...   a_n)^T, то рекурсивная программа вычисления этой суммы могла бы выглядеть так:

где S - вспомогательный параметр, в котором формируется значение требуемой суммы факториалов, а k - переменная, управляющая рекурсивными вызовами. Начальные значения S и k при обращении к sumf() должны быть равны соответственно a₀ и n.

Контрольный пример: