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 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."

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 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, 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.