Prolog infinite recursion not filling up the stack?

0
votes

Using the following example the stack quickly fills due to an infinite recursion...

is_pos_integer(X):- is_pos_integer(Y),X is Y+1.
is_pos_integer(0).

However, the following example when run and requested to backtrack (using ;), hits the same infinite recursion without filling up the stack...

is_pos_integer(0).
is_pos_integer(X):- is_pos_integer(Y),X is Y+1.

I don't believe either function is tail recursive, so why would the second one not cause a ........... StackOverflow? (yaaaaoww....sunglasses)

1
recursionprologstack-overflow
On what query and what Prolog system? - Eyal
Yes, neither example is tail recursive! And: Tail call optimization only applies if no choice points remain! The first example also needs to keep track of choice points. Also, one more elementary note: It is typically much better to describe positive integers with your Prolog system's CLP(FD) constraints, for example: positive_integer(I) :- I #> 0. - mat

1 Answers

2
votes

On the assumption that your query is something like ?- is_pos_integer(1) then the explanation is this:

The first example just goes into an infinite loop not subject to tail-recursion. So the stack fills up.

The second example will also fill up, eventually, but very slowly.

Let's label the first clause A and second clause B. When you call the first version of is_pos_integer(0), the call pattern is AAAAA... (out of stack). When you call the second version you get A (which returns to true to the top level) and then on backtracking BA which fails because 0 does not equal 0 + 1, then BBA which fail again because 0 does not equal 1 + 1, etc. You get call of BB...B(ntimes) and then A which fails. Eventually you will run out of stack, but it will take a very long time.