/* Some examples of recursion.
*
* member(X,List) succeeds if X is a member of List
* append(L1,L2,Ans) succeeds if Ans is the concatenation of
* L1 and L2
* get_n(L,Ans,N) succeeds if Ans is the list containing the
* first N elements of L
*/
member(X,[X|L]).
member(X,[_|L]) :- member(X,L).
append([X|L3],L4,[X|Ans1]) :- append(L3,L4,Ans1).
append([],L,L).
get_n([],[],_).
get_n([X|L1],[X|Ans1],N) :-
N>0,
N1 is N-1,
get_n(L1,Ans1,N1).
get_n(_,[],0).
/* A more elaborate example: the highest common factor of
* two numbers, using a simplistic version of Euclid's algorithm, viz.
* h.c.f. of M and N = h.c.f. of min(M,N) and M-N
* NOTE: the clauses given below ASSUME you're going to
* call hcf(M,N,Ans) with M>0, N>0, M>N. If you
* want to avoid this assumption, you should have
* a top-level predicate hcf1 (say), defined
*
* hcf1(M,N,Ans) :- tidy(M,N,Mnew,Nnew), hcf(Mnew,Nnew,Ans).
*
* where 'tidy' cleans up M and N. This is more
* efficient than just having another clause for hcf,
* since if you study the clauses below, you'll find
* that once the conditions are met, subsequent hcf goals
* also meet them.
* ALSO: note the use of the cuts to express "if you've got here,
* you've found the answer - no need to backtrack".
*/
hcf(M,N,Ans) :-
M=N,
Ans is N,
!.
hcf(M,N,Ans) :-
Z is M-N,
0 is N mod Z,
Ans is Z,
!.
hcf(M,N,Ans) :-
Z is M-N,
ZM, then max(N,M) > max(M,(N mod M)), so if
* you keep repeating this, the maximum steadily
* decreases. Therefore it must be zero at some point,
* and you know h.c.f. of 0 and X is just X.
*
* Subtle point (?): IF N =< M, then
* max(N,M) >= max(M,(N mod M)), so even in this
* case the maximum doesn't increase - though it may
* stay the same. THEREFORE, if we arrange to swap the
* arguments round at every step, the max must decrease
* at every other step!
*
* To avoid confusion, the predicate will be mcd in this
* version (= maximum common divisor).
* Again, note the use of the 'cut'.
*
* Compare hcf and mcd for speed! If you try
* hcf(10000,10,X), you'll have to wait a bit...
*/
mcd(N,0,N) :- !.
mcd(N,M,D) :- R is N mod M, mcd(M,R,D).