Factorial(N,FactN,NewI,NewP)

мал.6.4.

6.1. Написати рекурсивну і нерекурсивну програми, які обчислюють значення F(M,N) для довільної пари цілих чисел M,N>=0, яке визначається наступним чином:

ì M+N+1 якщо M*N=0

F(M,N)=í

î F(M-1, F(M,N-1)) в іншому випадку

6.2. N-те число Фіббоначі визначається наступним чином

ì 0 якщо N=0

F(N)=í 1 якщо N=1

î F(N-1)+F(M,N-1)) в іншому випадку

Написати рекурсивну і некурсивну програми, які обчислюють N-те число Фіббоначі.

6.3. Найбільший спільний дільник G(M,N) двох цілих чисел M і N можна визначити наступною рекурсивною схемою

ì M якщо N=0

G(M,N)=í

î G(N, MOD(M,N)) якщо N¹0

Написати програму, яка використовує рекурсивно-визначений предикат G(M,N), для визначення найбільшого спільного дільника декількох пар чисел.

Лабораторна робота №7

РЕКУРСИВНІ СТРУКТУРИ ДАНИХ

Рекурсивними можуть бути не тільки правила, а й структури даних. Пролог належить до тих мов програмування, в яких дуже зручно можна організовувати, описувати і реалізовувати дані рекурсивного типу. Тип даних буде рекурсивним, якщо він представляє собою структуру, яка в своєму визначенні використовує структуру, подібну собі.

Найбільш використовуваною рекурсивною структурою є список, але ми його розглянемо трішки пізніше. В цьому розділі ми зосередимо свою увагу на структурі даних типу дерева і на її використанні.

Структура даних типу дерева.

Серед структур даних типу дерева можна виділити спеціальний клас найбільш вживаних дерев- бінарні дерева. Можна дати наступне рекурсивне визначення бінарного дерева:

1.Пусте дерево- бінарне дерево.

2.Кожний вузел бінарного дерева має не більше одного лівого бінарного піддерева і не більше одного правого бінарного піддерева.

Таку структуру даних в Пролозі можна визначити за допомогою двох предикатів:

treetype = tree(string,treetype,treetype) та empty

Останній використовується для позначення пустого дерева. Тому структура даних для задання бінарного дерева може бути описана наступним чином:

Domains

treetype= tree(string, treetype,treetype);

Empty

Наприклад, дерево зображене на мал.7.1

C a t h y

/ \

/ \

M i c h a e l m e l o d y

/ \ / \

/ \ / \

C h a r l e s h a s e l j i m e l e o n o r

Мал.7.1.

може бути описане:

tree('Cathy',tree('Michael',tree('Charles',empty, empty),

tree('Hazel' ,empty, empty)),

tree('Melody', tree('Jim',empty, empty),

tree('eleanor' ,empty, empty)))

Відмітимо, що це не є прологівсьгою фразою; це є тільки складною структурою даних.