CS计算机代考程序代写 prolog algorithm Declarative Programming

Declarative Programming
Recursion

Geraint A. Wiggins

Professor of Computational Creativity
Department of Computer Science

Vrije Universiteit Brussel

Recursion in general

I Recursion is the idea of defining something in terms of
itself

I It is very closely bound up with the idea of mathematical
induction

I It allows us to make very clear statements of
algorithms. . .

I . . . because it is a very natural way to think

I Optimisations mean that programming recursively can be
efficient, too

Some Recursive Definitions

I In Prolog, a list is either an empty list or a term
connected by ‘.’ to another list

I Someone’s ancestor can be one of their parents or an
ancestor of one of their parents

I We can sort a list of numbers into order by picking out
the smallest, and then sorting the rest

I We can sort a list of numbers into order by picking one,
say X, dividing the rest into two groups, bigger and
smaller than X, sorting the two groups, and then
appending the results

I We can reverse a list of terms by taking the first element
off, reversing the rest, and putting the first element on
the end

Some Recursive Predicates
I Test if a term is a list

list( [] ).

list( [ |Tail] ) :- list( Tail ).
I Find an ancestor

ancestor( Old, Young ) :-

parent( Old, Young ).

ancestor( Old, Young ) :-

parent( Old, Middle ),

ancestor( Middle, Young ).

I Sort a list of numbers

sort( [], [] ).

sort( List, [Smallest|Sorted] ) :-
\+ List = [],
smallest( List, Smallest, Rest ),

sort( Rest, Sorted ).

Some Recursive Predicates

I Sort a list of numbers

sort( [], [] ).

sort( [First|Rest], Ans ) :-
split( First, Rest, Small, Big ),

sort( Small, Front ),

sort( Big, Back ),

append( Front, [First|Back], Ans ).
I Reverse a list

reverse( [], [] ).

reverse( [Head|Tail], Answer ) :-
reverse( Tail, RevTail ),

append( RevTail, [Head], Answer ).

Recursion in Prolog

I When we want to write recursive programs, we need to
think about two things:

1. How will the program terminate?
2. How will the program break up the data it works on?

I Recursion is an example of a divide-and-conquer strategy

Recursion in Prolog (2)

I To ensure that a program terminates, we must have at
least one base case – a non-recursive clause

I We must also ensure that something gets (in some sense)
smaller each time a recursion happens, so that we can say
when we have got to the end

I Example – testing if a term is a list:
I The base case is when we have an empty list – the

smallest list possible
I The recursive case breaks down a non-empty list into a

head and a tail. . .
I . . . and then tests the tail, so the thing being tested gets

smaller each time.

Recursion on explicit structures

I Testing if a term is a list

list( [] ).

list( [ |Tail] ) :- list( Tail ).
?- list( [a,b,c] ).

Call: list( [a,b,c] ).
Unify: [ |Tail] = [a,b,c]

Call: list( [b,c] ).
Unify: [ |Tail’] = [b,c]

Call: list( [c] ).
Unify: [ |Tail’’] = [c]

Call: list( [] ).

Recursion on explicit structures (2)

I Example: a binary tree datatype:
I Leaves are of form leaf( value )
I Branches are of form branch( Left, Right )

I Testing if a term is a binary tree

tree( leaf( X )).

tree( branch( X, Y )) :-

tree( X ),

tree( Y ).

I Note that we put the base case first!

Recursion on implicit structures

I An implicit datatype is one where there is no visible term
structure to control recursion

I Instead, the step along the datatype is defined by a
predicate, eg parent/2

I Example: parent/2

parent( john, jane ).

parent( jill, jane ).

parent( jane, jim ).

parent( jack, jim ).

I This forms an implicit binary tree, and we can use it to
control recursion just like an explicit one

Recursion on implicit structures (2)

I Example: ancestor/2

parent( john, jane ).

parent( jill, jane ).

parent( jane, jim ).

parent( jack, jim ).

ancestor( Old, Young ) :-

parent( Old, Young ).

ancestor( Old, Young ) :-

parent( Old, Middle ),

ancestor( Middle, Young ).

Recursion on implicit structures (3)

I Example run:

?- ancestor( john, jim ).

Call: ancestor( john, jim ).
Call: parent( john, jim ).
Fail.
Retry: ancestor( john, jim ).
Call: parent( john, Middle ).
Unify: Middle = jane.
Call: ancestor( jane, jim ).

Building recursive structures

I In Prolog, taking terms apart and building them are
nearly always the same thing.

I For example, in append/3:

append( [], List, List ).

append( [H|T], List, [H|BigList] ) :-
append( T, List, BigList ).

I Arguments 1 and 3 are both “broken down” or “built up”
by unification; we don’t usually use both as inputs

I Exercise 2 shows how append/3 can be used both to split
up a list and to join lists together

I This is one reason why it is better not to think of
predicates as having “outputs” at all

Building recursive structures (2)

I In the examples so far, the answer has been built up in
reverse of the breakdown of the input (no matter which
way round they are)

I Alternatively, we can use an accumulator argument to
build up an answer as we break down the input (or vice
versa)

I Example, reverse/3:

reverse( [], Answer, Answer ).

reverse( [H|T], SoFar, Answer ) :-
reverse( T, [H|SoFar], Answer ).

?- reverse( List, [], Answer ).

(This is an example of tail-recursive optimisation.)

Building recursive structures (3)

I Example run of reverse/3:

?- reverse( [a,b,c], [], Ans ).

Call: reverse( [a,b,c], [], Ans ).
Unify: [a,b,c] = [H|T], SoFar = []

Call: reverse( [b,c], [a], Ans ).
Unify: [b,c] = [H’|T’], SoFar’ = [a]

Call: reverse( [c], [b,a], Ans ).
Unify: [c] = [H’’|T’’], SoFar’’ = [b,a]

Call: reverse( [], [c,b,a], Ans ).
Unify: Ans = Answer, Answer = [c,b,a]