I've seen the Prolog Prologue definition of between/3:
between(Lower, Upper, Lower) :-
Lower =< Upper.
between(Lower1, Upper, X) :-
Lower1 < Upper,
Lower2 is Lower1 + 1,
between(Lower2, Upper, X).
I don't understand why it requires recursion. A logical definition of between could be:
between(Lower, Upper, Something):-
Lower =< Upper,
Lower =< Something,
Something =< Upper.
I tried that on gprolog and it works, but only for simple queries:
| ?- between(0,5,1).
yes
For queries with variables I get:
| ?- between(0,5,X).
uncaught exception: error(instantiation_error, (=<)/2)
I don't really understand why.
I kind of figure Prolog needs some sort of reference number to unify variables against, but why the cryptic error on (=<)/2?
The error is not that cryptic, once you know what general purpose arithmetic in Prolog does. In short, it is simply there to do non-logical, "calculate this and give me the answer" kind of arithmetic. Comparisons (so all the </2, =</2, =:=/2, etc) require that you have arithmetic expressions on both sides; is/2 assumes that it has an arithmetic expression on the left side and a free variable on the right. So, you can do stuff like:
?- X is 3^1.3.
X = 4.171167510947728.
?- 1 =:= sin(pi/2).
true.
If you actually read the GNU-Prolog manual carefully enough, you should find, at the beginning of the relevant section, the following two sentences:
An arithmetic expression is a Prolog term built from numbers, variables, and functors (or operators) that represent arithmetic functions. When an expression is evaluated each variable must be bound to a non-variable expression.
(Emphasis mine)
Predicates like between/3, plus/3, or succ/2 are examples of special purpose integer arithmetic. They have their uses. However, most of the uses for doing actual integer math have been superseded by CLPFD. For GNU-Prolog, you should consult the documentation, but for a short example, to emulate between/3, you could say:
?- fd_domain(X, 0, 2), fd_labeling(X).
X = 0 ? ;
X = 1 ? ;
X = 2
yes
You should notice that this is definitely not recursive (to answer the question in the title). Of course, we are all aware that at some level, there is recursion or iteration involved, in order to get these answers.