Лекция: Return x;

default:

return 2 * x * T (n — 1, x) — T (n — 2, x);

}

}

Как видно из этих примеров алгоритм, реализуемый через рекурсию, выглядит более компактным и понятным по сравнению с обычной реализацией. С точки зрения эффективности, реализацию этих примеров через рекурсию вряд ли можно считать более эффективной, чем обычную реализацию. Это объясняется дополнительными затратами времени на многократный вызов функций и дополнительными затратами памяти (стека) на передачу аргументов.

Однако в ряде случаев использование рекурсии позволяет достичь существенного положительного эффекта.

Рассмотрим следующий пример: необходимо написать функцию для вычисления биномиальных коэффициентов:

n >= 0, 0 <= m <= n.

Значение биномиального коэффициента определяет число различных вариантов выбора m объектов из n объектов (как говорят, число сочетаний из n по m).

Основные свойства биномиальных коэффициентов:

Максимальное значение биномиального коэффициента достигается при m = n / 2.

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