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]