Вопрос 11) Рекурсия (Prolog)

Рекурсия - один из основных приёмов программирования в декларативных языках, какими являются Пролог и Лисп. Предикат или функция называются рекурсивными, если они ссылаются на самих себя. При этом задача разбивается на части все меньшего и меньшего размера до тех пор, пока они не станут настолько малы, что их решение не будет сводиться к набору из одной или нескольких простейших операций.

Обычно рекурсивная программа состоит как минимум из двух частей:

1. граничного условия, при котором рекурсия останавливается;

2. рекурсивного условия, при котором в описание функции или предиката входит и сама функция или предикат.

Механизм рекурсии часто объясняют на вычислениях чисел Фибоначчи, первые 10 которых приведены в таблице:

Числа Фибоначчи (первые 10 значений)
Номер числа Фибоначчи	0	1	2	3	4	5	6	7	8	9	10
Значение числа Фибоначчи	1	1	2	3	5	8	13	21	34	55	89

Здесь каждое следующее число представляет собой сумму двух предыдущих чисел.

Эти числа могут быть определены следующим соотношением:

fib(0) = 1

fib(1) = 1

fib(n) = fib(n-1) + fib(n-2)

На Прологе это соотношение будет выглядеть так:

predicates

fib(integer,integer)

clauses

fib(0,1). % граничное условие

fib(1,1). % граничное условие

fib(N,F) :- N>1,

N1=N-1,

fib(N1,F1),

N2=N-2,

fib(N2,F2),

F=F1+F2.

Теперь Goal: fib(10,X).

89

На рисунке представлена схема вычисления числа Фибоначчи с помощью рекурсии.

Другая функция, вычислять которую удобно с применением рекурсии, - это факториал числа N (записывается N!, произносится "эн-факториал"). По определению, 0! равен 1. Остальные значения определяются формулой:

N!=N·(N-1) · (N-2) ·…·2·1.

Первые десять значений факториала
N	0	1	2	3	4	5	6	7	8	9	10
N!	1	1	2	6	24	120	720	5040	40320	362880	3628800

Рекурсивно функцию факториала можно описать так:

0!=1

N!=N*(N-1) для N>0

Программа, реализующая функцию факториала числа n! в Прологе, выглядит так:

predicates

fact (integer, real)

clauses

fact.(N,F):-N<0,!,fail.

fact(0,1).

fact(N,F):-N1=N-1,

fact(N1,F1),

F=F1*N.

Зададим затем   Goal: fact(4, X) и получим решение:   Х=24   1 Solution