Стр. 14 - Основы алгоритмов и структур данных

12 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
В любом случае рекурсия должна быть конечной, то есть с каждым
рекурсивным вызовом задача должна некоторым образом упрощаться, так,
чтобы, в конце концов, сводиться к некоторому частному случаю, имеющему
тривиальное решение.
Пример. Вычисление факториала n!=n*(n-1)!, n>0.
M=FACT(N);
int FACT(int K)
{
IF (K>1) THEN RETURN (K*FACT(K-1)); - рекурсивная ветвь
ELSE RETURN (1); - нерекурсивная ветвь (самая глубокая)
}
3.2. Методика решения рекурсивной задачи
Если задача может быть разложена на совокупность задач того же типа, но
меньшей размерности (как с факториалом), то методика анализа данной задачи
содержит три этапа.
1. Параметризация задачи: выделяются все элементы, от которых зависит
решение и в, частности, размерность задачи, причём эта размерность должна,
очевидно, убывать после каждого рекурсивного вызова. Результат
параметризации с точки зрения программирования – список аргументов.
2. Поиск тривиального случая и его решение. Тривиальный случай –
ключевой этап, который может быть решён без рекурсии. При этом
размерность задачи равна 1 или 0.
3. Декомпозиция общего случая, имеющая целью свести его к одному из
нескольких более простых случаев (меньшей размерности).
В любом случае от вызова к вызову размерность задачи должна
уменьшаться. Если задача не будет удовлетворять этому требованию, то
решать её с помощью рекурсии нельзя.