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

## Exiting 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."*

## 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 `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.

## Advice

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.