here is the trace without the cut
[trace] 21 ?- odd(s(s(s(0)))).
Call: (6) odd(s(s(s(0))))
Call: (7) odd(s(0))
Exit: (7) odd(s(0))
Exit: (6) odd(s(s(s(0))))
true ;
Redo: (7) odd(s(0))
Fail: (7) odd(s(0))
Fail: (6) odd(s(s(s(0))))
false.
and here with the cut
[trace] 22 ?- odd(s(s(s(0)))).
Call: (6) odd(s(s(s(0))))
Call: (7) odd(s(0))
Exit: (7) odd(s(0))
Exit: (6) odd(s(s(s(0))))
true.
I think the cut has been added for efficiency...
About s/1, it's not a predicate, but a data structure. Maybe you've seen something like
integer(0).
integer(s(X)) :- integer(X).
that's actually the simplest recursive definition for the infinite domain of (positive) integers