DE → EN A-AA+ Sitemap Suche

# 3    Listen, Rekursion

## 3.1    Familienbeziehungen

``````vorfahr( VF, M) :-
elter( VF, M).
vorfahr( VF, M) :-
elter( Elter, M),
vorfahr( VF, Elter).

nachkomme( NK, M) :-
kind( NK, M).
nachkomme( NK, M) :-
kind( Kind, M),
nachkomme( NK, Kind).
/* auch: nachkomme( NK, M) :-
vorfahr( M, NK) */

verwandt( X, Y) :-
vorfahr( X, Y).
verwandt( X, Y) :-
nachkomme( X, Y).
verwandt( X, Y) :-
vorfahr( Z, X),
vorfahr( Z, Y),
X \= Y.
``````

Back to example 3.1

## 3.2    Fakultät & Fibonacci

``````fakultaet( 0, 1).
fakultaet( X, Y) :-
X > 0,
X1 is X - 1,
fakultaet( X1, Y1),
Y is X*Y1.

fibo( 0, 1).
fibo( 1, 1).
fibo( X ,Y) :-
X > 1,
X1 is X-1,
X2 is X-2,
fibo( X1, Y1),
fibo( X2, Y2),
Y is Y1 + Y2.
``````

Back to example 3.2

## 3.3    Listenmanipulation

``````member( X, [ X| _]).
member( X, [ _| Y]) :-
member( X, Y).

append( [], Y, Y).
append( [ X1| X], Y, [ X1| Z]) :-
append( X, Y, Z).

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

/* accumulator */
rev( X, Y) :-
rev( X, [], Y).
rev( [ X1| X], Y0, Y) :-
rev( X, [ X1| Y0], Y).
rev( [], Y, Y).

min_list( [ X], X).
min_list( [ X1| Xs], MinX) :-
min_list( Xs, MinXs),
min( X1, MinXs, MinX).

min( X, Y, X) :- X =< Y.
min( X, Y, Y) :- X > Y.

sum( [ X], X).
sum( [ X1| Xs], S1) :-
sum( Xs, S),
S1 is S + X1.

length( [], 0).
length( [ X| Xs], L) :-
length( Xs, Ls),
L is Ls + 1.

positive( [], []).
positive( [ X1| X], [ X1| Y]) :-
X1 > 0,
positive( X, Y).
positive( [ X1| X], Y) :-
X1 =< 0,
positive( X, Y).

flatten( [], []).
flatten( [ X1| Xs], Y) :-
flatten( X1, Y1),
flatten( Xs, Ys),
append( Y1, Ys, Y).
flatten( X, [ X]) :-
not_list( X).
not_list( X) :-
X \= [],
X \= [ _| _].

set( [], []).
set( [ X1| Xs], Ys) :-
member( X1, Xs),
set( Xs, Ys).
set( [ X1| Xs], [ X1| Ys]) :-
not_member( X1, Xs),
set( Xs, Ys).

not_member( X, []).
not_member( X, [ Y| Ys]) :-
X \= Y,
not_member( X, Ys).

sort( [], []).
sort( [ X1| Xs], Y) :-
sort( Xs, Ys),
insert( X1, Ys, Y).

insert( X, [], [ X]).
insert( X, [ Y1| Ys], [ X, Y1| Ys]) :-
X =< Y1.
insert( X, [ Y1| Ys], [ Y1| Zs]) :-
X > Y1, insert( X, Ys, Zs).
``````

Back to example 3.3

## 3.4    Ein komplexes Velo

``````teile( S, Teile) :-
struktur( S, Ks),
teile_k( Ks, Teile).

teile_k( [], []).
teile_k( [ K1| Ks], T) :-
teile_k1( K1, T1),
teile_k( Ks, T2),
append( T1, T2, T).

teile_k1( S, [ S] ) :-
element( S).
teile_k1( S, T ) :-
teile( S, T).

teil( S, K) :-
struktur( S, Ks),
member( K, Ks).
teil( S, K) :-
struktur( S, Ks),
member( S1, Ks),
teil( S1, K).
``````

Back to example 3.4