![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
default:
return 2 * x * T (n - 1, x) - T (n - 2, x);
}
}
Как видно из этих примеров алгоритм, реализуемый через рекурсию, выглядит более компактным и понятным по сравнению с обычной реализацией. С точки зрения эффективности, реализацию этих примеров через рекурсию вряд ли можно считать более эффективной, чем обычную реализацию. Это объясняется дополнительными затратами времени на многократный вызов функций и дополнительными затратами памяти (стека) на передачу аргументов.
Однако в ряде случаев использование рекурсии позволяет достичь существенного положительного эффекта.
Рассмотрим следующий пример: необходимо написать функцию для вычисления биномиальных коэффициентов:
n >= 0, 0 <= m <= n.
Значение биномиального коэффициента определяет число различных вариантов выбора m объектов из n объектов (как говорят, число сочетаний из n по m).
Основные свойства биномиальных коэффициентов:
Максимальное значение биномиального коэффициента достигается при m = n / 2.
Очевидная реализация функции основана на использовании циклов для вычисления числителя и знаменателя биномиального коэффициента и нахождения частного от их деления:
Дата публикования: 2014-11-28; Прочитано: 217 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!