Линейная рекурсия
Home Up Next

Рекурсия, при которой рекурсивные вызовы на любом рекурсивном срезе, инициируют не более одного последующего рекурсивного вызова, называется линейной. Это наиболее простой и часто встречающийся тип рекурсии. Большая часть ранее разобранных примеров относилась именно к этому типу рекурсии. Еще один пример линейной рекурсии.

Пусть коэффициенты многочленов fn(x) и gm(x) степеней n и m (n, m³0) соответственно заданы компонентами векторов v и w:

Пусть далее при m=0, то есть если gm(x) есть константа, gm(x)¹0. Составить программу-функцию нахождения частного q(x) и остатка r(x) при делении fn(x) на gm(x):

fn(x) = q(x)×gm(x) + r(x),                                                  (1)

где степень r(x) меньше m (при m=0 r(x)º0).

Решение. Представление (1) единственно. В дальнейшем нам удобно считать, что степень r(x) не выше m с возможно нулевыми коэффициентами при старших степенях x.

При n£m имеем

                     (2)

Пусть n>m. Введем обозначение

Отсюда

                                               (3)

где fn- 1(x) - многочлен, степени не выше n- 1. Если для fn- 1(x) найдено q1(x) и r1(x) - частное и остаток от деления на gm(x), то вместе с (1) и (3) это дает:

                                                          (4)

Если соотношения (2) рассматривать в качестве базы рекурсии, то равенства (4) определяют декомпозицию. Считаем, что в результате вычислений должен быть сформирован и возвращен составной вектор qr = [q   r]T, где q и r - соответственно векторы коэффициентов многочленов q(x) и r(x). Соответствующая программа-функция, реализующая эти идеи, выглядит так:

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

     

     

Home Содержание Схемы ООД Доска объявлений Поиск