Subject: Re: http://www.swi.psy.uva.nl/projects/SWI-Prolog/recursive or not

From: "Richard A. O'Keefe" <[email-masked]>
Date: Mon, 3 Apr 2000 12:37:20 +1200 (NZST)

"Iva" ([email-masked]) wrote:
	
	I find it a bit difficult to understand wheather Proog is recursive or not.
	Sorry, that was Prolog. I am currently learning SWI-Prolog on unix and 
	understanding what  recursive is meant to be in the prolog sense 
	is a bit complicated. Could someone give an example of a recursive
	program using lists with an explanation.
	
There *isn't any* "Prolog sense" of 'recursive'.
A definition is recursive if the thing defined is used in its own definition.
That's the definition of "recursive" for C, Lisp, Prolog, Smalltalk, COBOL,
you name it.
	
The classic example of a recursive list-processing definition in Prolog is

    %   append(Xs, Ys, XYs)
    %   is true if Xs is a list and XYs is obtained by gluing the elments
    %   of Xs in front of Ys.  (Ys doesn't have to be a list, but you will
    %   confuse people, including yourself, if it isn't.)

    append([], L, L).
    append([H|T], L, [H|R]) :-
	append(T, L, R).

The definition of append/3 uses append/3, so append/3 has a recursive
definition.  In exactly the same way, you would write

    (define (append Xs Ys)
	(if (null? Xs)
	    Ys
	    (cons (car Xs) (append (cdr Xs) Ys))))

in Scheme, where the definition of append - - is recursive because
append is used in it, or you might write

    append :: [t] [t] -> [t]
    append [] ys = ys
    append [x:xs] ys = [x:append xs ys]

in Clean, where again append is used in its own definition.

More generally, you could call this "direct" recursion, because append
is used directly in its own definition.  "Indirect" recursion is where
the definition of A uses B, the definition of B uses C, ..., the
definition of Z uses A, as in

    even_length([]).
    even_length([_|T]) :- odd_length(T).

    odd_length([_|T]) :- even_length(T).

Here the definition of even_length/1 uses odd_length/1, and the
definition of odd_length/1 uses even_length/1, so even_length/1
is (indirectly) recursive (and so is odd_length/1).