Recursion in prolog is pretty much identical to recursion in any other language. The trick with prolog is that

- every variable is local, and,
- once unified, variables cease to be variables. They can never change value.

This means that you'll often need to build what I'll call "worker" predicates that do that the actual work required and carry around 1 or more variables that act as working storage. Here is an implementation of sum/2 to sum a list of integers:

```
% 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 ).
```

Here is an implementation in ANSI C that closely mirrors the above prolog code:

```
#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 ;
}
```

## comments: