Рекурсия, при которой рекурсивные вызовы на любом рекурсивном срезе, инициируют не более одного последующего рекурсивного вызова, называется линейной. Это наиболее простой и часто встречающийся тип рекурсии. Большая часть ранее разобранных примеров относилась именно к этому типу рекурсии. Еще один пример линейной рекурсии.
Пусть коэффициенты многочленов 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). Соответствующая программа-функция, реализующая эти идеи, выглядит так:Контрольные примеры: