адача 9. Составить рекурсивную программу-функцию вычисления биномиальных коэффициентов        С(n,m), где n и m - целые и 0£ m£ n.

Решение. Известно, что

Отсюда и вытекает справедливость следующего рекурсивного определения С(n,m):

Обратите внимание на то, что здесь мы имеем рекурсию сразу по двум аргументам.

Опираясь на функцию C(n,m) как на подпрограмму, построим функцию binom(n,k), возвращающую для целого n ³ 0 вектор из k последовательных биномиальных коэффициентов: С(n,0), C(n,1),…,C(n,k) (k£ n).

Решение данной задачи можно записать так:

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

Замечание. Для отыскания всех биномиальных коэффициентов при заданном n не обязательно вычислять binom(n,n). Учитывая, что C(n,k)=C(n,n- k), достаточно вычислить binom(n,(n- mod(n/2))/2).

И еще один способ вычисления биномиальных коэффициентов. Рекурсивная программа-функция tripas(n) вычисляет треугольник Паскаля, то есть значения величин C(i, j) для (0£ j£ i£ n), исходя из формул, непосредственно определяющих и декомпозицию, и базу:

Справа от функции просчитан контрольный пример для n=4.

Вычисления по tripas(n) реализуются не более чем за n рекурсивных обращений, при этом общее количество операций сложения не превосходит величины n² / 2.

Для вывода лишь последней строки треугольника Паскаля рекурсивную функцию tripas() можно модифицировать так:

   tripa(4)^T = [1   4   6   4   1].