Рекурсия в прологе практически идентична рекурсии на любом другом языке. Хитрость с прологом в том, что
- каждая переменная является локальной, и,
- после объединения переменные перестают быть переменными. Они никогда не могут изменить значение.
Это означает, что вам часто нужно будет создавать то, что я буду называть «рабочими» предикатами, которые выполняют реальную работу и содержат около 1 или более переменных, которые действуют как рабочее хранилище. Вот реализация sum / 2 для суммирования списка целых чисел:
% sum/2
sum( [] , 0 ).
sum( [X|Xs] , Total) :-
sum(Xs,X,Total).
% sum/3 (worker predicate)
sum( [], Total, Total ).
sum( [X|Xs] , Subtotal , Total ) :-
NewSubTotal is Subtotal + X ,
sum( Xs , NewSubTotal , Total ).
Вот реализация в ANSI C, которая близко отражает вышеприведенный код пролога:
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
// linked list structure
typedef struct listnode
{
int value ;
struct listnode *next ;
} LISTNODE ;
// core recursive worker function
int sum_core( int subtotal , LISTNODE *list )
{
LISTNODE *head ;
LISTNODE *tail ;
int list_item ;
if ( list == NULL ) return subtotal ;
head = list ;
tail = list->next ;
list_item = head->value ;
return sum_core( subtotal + head->value , tail ) ;
}
// external interface
int sum( LISTNODE *list )
{
LISTNODE *head ;
LISTNODE *tail ;
int list_item ;
if ( list == NULL ) return 0 ;
head = list ;
tail = list->next ;
list_item = head->value ;
return sum_core( list->value , tail ) ;
}
int main ( int argc , char * argv[] )
{
LISTNODE *list ;
int total ;
list = malloc(sizeof(LISTNODE)) ; list->value = 1 ;
list->next = malloc(sizeof(LISTNODE)) ; list->next->value = 2 ;
list->next->next = malloc(sizeof(LISTNODE)) ; list->next->next->value = 3 ;
list->next->next->next = NULL ;
total = sum( list ) ;
return ;
}