Basic Idea Of Recursion

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 looping-until-valid 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 only need their first valid answer. Our recursive call is only made if number/1 fails. So when you type in "pickles.", Prolog checks number(pickles), which will fail. But Prolog sees the ; disjunction and checks 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, it 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."

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 (a condition that stops it) exits the recursion.

Ask for the 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 CD with 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, 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, practise 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.

Until next time, Happy Prologing!

Paul