#   # Learning Pilog - 4: Recursion

In the last post, we discussed briefly the backtracking search algorithm. Let's explore this topic a little further as it's an important concept in Pilog programming.

This post is based on this tutorial.

### A recursive example

Let's illustrate the concept of recursion on a little silly example. Let's say we define two rules for `@X` "digesting" `@Y`: either `@X` has just eaten `@Y`, or `@X` has eaten something that has eaten `@Y`.

``````(be is_digesting (@X @Y)
(just_ate @X @Y) )

(be is_digesting (@X @Y)
(just_ate @X @Z)
(is_digesting @Z @Y) )
``````

Now let's travel up a whole food chain. A mosquito has been biting John. That mosquito got then eaten by a frog who got eaten by a stork.

``````(be just_ate (Mosquito (blood John)))
(be just_ate (Frog Mosquito ))
(be just_ate (Stork Frog))
`````` Now, what is the Stork digesting? Let's ask Pilog!

``````:  (? (is_digesting Stork @X))
@X=Frog
@X=Mosquito
@X=(Blood John)
-> NIL
``````

The stork is digesting a frog, a mosquito, and John's blood. Bon appetit!

### The order matters

The digestion example was pretty straightforward. However, one thing needs to be understood when we talk about recursion: The order matters - not for the underlying logic, but for the computation in Pilog.

We said, something is digesting `@X` if:

1. it has eaten `@X` or
2. has eating something that has eaten `@X`.

From logic point of view, we could also reverse 1. and 2., and nothing will change.

``````(be is_digesting (@X @Y)
(just_ate @X @Z)
(is_digesting @Z @Y) )

(be is_digesting (@X @Y)
(just_ate @X @Y) )
``````

The output is the same as in the previous question, just top-down: We get the lowest level first.

``````:  (? (is_digesting Stork @X))
@X=(Blood John)
@X=Frog
@X=Mosquito
-> NIL
``````

Why? Because Pilog is checking if there is a successor (`(just_ate @X @Z)`) before it checks the direct connection `(just_ate @X @Y)`. This corresponds to a different traversal in a tree search (some examples can be found in the PicoLisp example of this Rosetta code task).

### How NOT To Do It

Now let's try another variant which also seems okay from logic point of view:

``````(be is_digesting (@X @Y)
(is_digesting @Z @Y)
(just_ate @X @Z) )

(be is_digesting (@X @Y)
(just_ate @X @Y) )
``````

What is different? Instead of checking first if an item `@Z` has been eaten by `@X`, we check if `@Z` is digesting `@Y`. We run our same query again - unfortunately, this calculation never terminates!

``````
: (? (is_digesting Stork @X))
@X=Frog
@X=Mosquito
@X=(blood John)
``````

Instead of terminating, the REPL keeps on printing empty lines and we have to cancel with `^C`. Let's trace it again to see what is happening. Again, we can print out the current rules with `(rules <predicate(s)>)`:

``````: (rules 'is_digesting 'just_ate)
1 (be is_digesting (@X @Y) (just_ate @X @Y))
2 (be is_digesting (@X @Y) (is_digesting @Z @Y) (just_ate @X @Z))
1 (be just_ate (Mosquito (blood John)))
2 (be just_ate (Frog Mosquito))
3 (be just_ate (Stork Frog))
``````

Now we start the query in trace mode, i.e. `(? <predicate(s)> (<predicate> <args>))`. The beginning looks OK:

``````: (? is_digesting just_ate (is_digesting Stork @X))
1 (is_digesting Stork @Y)
3 (just_ate Stork Frog)
@X=Frog
``````

`@X` is unified with `Frog` due to the first clause of `is_digesting` and the third clause of the `just_ate` predicate.

``````2 (is_digesting Stork @Y)
1 (is_digesting @X @Y)
1 (just_ate Mosquito (blood John))
2 (just_ate Frog Mosquito)
3 (just_ate Stork Frog)
@X=Mosquito
``````

Then the `Mosquito` is found using the second rule of the `is_digesting` predicate, which is looking for an `@Y` that is currently being digested. The Mosquito is digested by the frog (Rule 2). Similarly, `(blood John)` is also found.

However, if we then press `<Enter>`, we get a neverending loop of printouts of the following lines:

``````2 (is_digesting @X @Y)
1 (is_digesting @X @Y)
1 (just_ate Mosquito (blood John))
2 (just_ate Frog Mosquito)
3 (just_ate Stork Frog)
2 (just_ate Frog Mosquito)
3 (just_ate Stork Frog)
3 (just_ate Stork Frog)
``````

What is happening? Like in the examples above, Pilog is trying to find something that "just ate" `@Y`. But since there is no termination condition for the loop, Pilog tries to recursively replace `@Y` by something that is "not Stork" in order to find a solution, and gets into an infinite loop.

This is called left recursion and is the root cause of our problem.

### Example: Travel plans Now let's use recursion to solve this little task: Using Pilog to tell us if we can get from A to B using the pre-defined resources.

``````(be directTrain (Saarbruecken Dudweiler))
(be directTrain (Forbach Saarbruecken))
(be directTrain (Freyming Sorbach))
(be directTrain (StAvold Freyming))
(be directTrain (Fahlquemont StAvold))
(be directTrain (Metz Fahlquemont))
(be directTrain (Nancy Metz))
``````

Obviously, we can directly travel between two cities if there is a direct train.

``````(be travelBetween (@X @Y)
``````

In case there is no direct train, we can solve it by recursion: We search for another station `@Z` that is reachable from `@X`, and check if that station `@Z` is connected to `@Y`:

``````(be travelBetween (@X @Y)
(directTrain @X @Z)
(travelBetween @Z @Y))
``````

Now let's quickly consider what happens if we implement the other way round. Probably if there's a train from X to Y, then there should also be a train from Y to X, right?

So does that mean that we can do something like this - expanding our previous example by simply swapping `@X` and `@Y` in each line?

``````(be travelBetween (@X @Y)
(directTrain @X @Y))

(be travelBetween (@Y @X)
(directTrain @Y @X))

...
``````

Unfortunately not. Since we can go in both directions, we can end up in infinite loops, travelling between `X` and `Y` and neever getting any further.

In order to implement something like this, we need to be able to "cut" a search tree after a given result - we will discuss in a further post how to do this.

In the next post, we will see how to work with lists in Pilog, a concept that we also frequently see in "normal" PicoLisp.