Basic Idea of Recursion
Want to do something a bunch of times in Prolog? Recursion is how we do it. In this post we'll look at the most basic ideas of recursion and talk through a couple of examples.
recursive: defined in terms of itself
Simple?! It means for a predicate to qualify as recursive it must include itself as a sub-goal. Thus the simplest, and most useless recursive predicate one could write would be:
warm_up_cpu :- warm_up_cpu. So in practical terms, there's a little more to using the idea than just that.
For nearly all recursive predicates, we want them to end their computation at some point. This means we need an exit clause. As Prolog checks from top-to-bottom, typically we put the exit clause for checking first. Then we'll put some predicate to do what we want. The simplest use-case here is in getting user input, this potentially infinite recursion is a great way to validate user input. In this example we only want to read once, so we use the
; operator for disjunction within a single clause.
Don't forget to terminate your input with a full-stop!
So in this example we read some user input, which for our imaginary application needs to be a number. Our exit goal is
number/1, if this validates then we
! cut to remove the following choice-point left by
; read_number(N) as we're imagining only needing their first valid answer. Our recursive call is only taken if
number/1 fails. So when you type in "pickles." Prolog checks
number(pickles), which will fail. But Prolog see's the
; disjunction and goes to check if that other side will succeed.
That's where Prolog finds the recursive call back to
read_number(N) and in trying to prove that will once again ask you for input with
read/1, which it tries to validate again with
number/1. This repeats until you input some number such as "42."
Towards A Goal
Typically when doing recursion we're moving towards some goal, so our recursive call should accomplish this task. In this example we also combine the exit clause with the recursive call in the same body. In this case the exit clause is when the number is 0, but the recursive call needs to be guarded from numbers less than 0 to prevent infinite recursion. The guard exits the recursion.
Ask for Next Answer until you get to false to see the recursion in play:
When we call
countdown(5, CD), Prolog first checks if
5 > 0, our exit clause, it succeeds so next sub-goal. Now Prolog checks if
Less1 is 5 - 1 and decides that
Less1 unifies with
4, so next sub-goal. This next sub-goal is disjunctive, only one side of the
; operator needs to succeed for
countdown/2 to succeed. Prolog begins with the left-hand side and tries to unify
4, which it can do. At this point Prolog tells us
countdown(5, 4) succeeds and that there's a choice-point left so we can backtrack.
This choice-point is the right-hand side of the
; operator, so if we ask Prolog for another solution it finds itself trying to prove
countdown(4, CD), as
Less1 is unified to 4 at this point. When
countdown(4, CD) has been proven to succeed if
CD unifies with
3, as this
CD is the same
CD as in the head of the clause we're trying to prove:
countdown(5, CD), Prolog will tell us
countdown(5, 3) also succeeds. This continues until Prolog is trying to prove
countdown(0, CD), when it tests if
0 > 0, this fails, there are no further choice-points, and so Prolog fails the query.
The best thing you can do to understand recursion if you're struggling with tracing how it executes is to grab a pencil and paper and write out the goals for a small example like
countdown(3, N). If you've not got your head around unification yet though, do that first!
As ever, practice makes perfect. You could try writing a predicate to read user input that must be one of rock, paper, or scissors. Then try a square-root approximation predicate, here's a YouTube video describing the algorithm. If you want a fun project, you'll find a couple of places for recursion in the classic "higher/lower" guess a number game: accepting valid user input and guessing again.