В математике рекурсия определяется как способ описания объектов, данных, процессов или функций через самих себя. представляют собой как раз такое описание. В них процесс на n-ом шаге определяется через тот же самый процесс на n-1-м шаге. Чтобы перейти к рекурсивному определению в программе, необходимо для описания процесса определить предикат, который обращался бы к самому себе (т.е. к описанию того же процесса) при других значениях аргументов (например, при другом номере шага K!=K-1). При этом как бы допускается, что уже имеется описание процесса, которое правильно выполняется для аргумента K-1 и, следовательно, позволяет получить состояние yk-i на предшествующем шаге. Например, рекуррентным соотношениям, описывающим процесс вычисления факториала F=N! (пример 1) и вычисления чисел Фибоначчи (пример 2), можно поставить в соответствие следующие программы на Прологе
Пример 1
/* Нисходящая рекурсия */
/*0!=1; */ 'факт' (0,1):-!. /* начальные условия */
'факт' (K,F):- /* текущее состояние */
/* на шаге k */
/*K=N,N-1,...,0;*/
K1 is K-1, /*K1 - номер предыдущего */
/* шага */
/*F1=(K-1)!;*/ 'факт' (K1,F1), /* F1 – предшествующее */
/* состояние */
/*K!=(K-1)!*K;*/ F is F1*K. /* определение текущего */
/* состояния */
?- 'факт' (3,F). /* запрос */
Пример 2
/* Нисходящая рекурсия */
/*f0=0; */ 'фибоначчи' (0,0):-!. /* начальные */
/*f1=1; */ 'фибоначчи' (1,1):-!. /* условия */
'фибоначчи' (K,F):-
K1 is K-1,
/*fk-1; */ 'фибоначчи' (K1,F1), /* F(K-1) */
K2 is K-2,
/*fk-2; */' ‘фибоначчи' (K2,F2), /* F(K-2) */
/*fK=fK-1+fK-2;*/ F is F1+F2. /*F(K)=F(K-1)+F(K-2) */
?- 'фибоначчи' (10,Z). /* запрос */
Из примеров следует, что если процесс описан рекуррентными соотношениями типа (1), то формально переход к рекурсивному описанию на Прологе осуществляется достаточно просто.
|
Главная
Каталог файлов
