CODEWITHSUNDEEP
recursionprologstack-overflow
Andrew
Andrew

Reputation: 617

Prolog infinite recursion not filling up the stack?

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)

Upvotes: 0

Views: 124

Answers (1)

Eyal
Eyal

Reputation: 1110

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.

Upvotes: 2

Related Questions