Editing Recursive definition (section)

==Recursive definitions as logic programs==
{{See also|Definition#Logic programs}}
[[Logic programming|Logic programs]] can be understood as sets of recursive  [[definition]]s.<ref>Denecker, M., Ternovska, E.: A logic of nonmonotone inductive definitions. ACM
Trans. Comput. Log. 9(2), 14:1–14:52 (2008)</ref><ref>Warren, D.S. and Denecker, M., 2023. A better logical semantics for prolog. In Prolog: The Next 50 Years (pp. 82-92). Cham: Springer Nature Switzerland.</ref> For example, the recursive definition of even number can be written as the logic program:

<syntaxhighlight lang="prolog">
even(0).
even(s(s(X))) :- even(X).
</syntaxhighlight>

Here <syntaxhighlight lang="prolog" inline>:-</syntaxhighlight> represents ''if'', and <syntaxhighlight lang="prolog" inline>s(X)</syntaxhighlight> represents the successor of <syntaxhighlight lang="prolog" inline>X</syntaxhighlight>, namely <syntaxhighlight lang="prolog" inline>X+1</syntaxhighlight>, as in [[Peano arithmetic]]. 

The logic programming language [[Prolog]] uses [[backward chaining|backward reasoning]] to solve goals and answer queries. For example, given the query <syntaxhighlight lang="prolog" inline>?- even(s(s(0)))</syntaxhighlight> it produces the answer <syntaxhighlight lang="prolog" inline>true</syntaxhighlight>. Given the query <syntaxhighlight lang="prolog" inline>?- even(s(0))</syntaxhighlight> it produces the answer <syntaxhighlight lang="prolog" inline>false</syntaxhighlight>.

The program can be used not only to check whether a query is true, but also to generate answers that are true. For example:

<syntaxhighlight lang="prolog">
?- even(X).
X = 0
X = s(s(0))
X = s(s(s(s(0))))
X = s(s(s(s(s(s(0))))))
.....
</syntaxhighlight>

Logic programs significantly extend recursive definitions by including the use of negative conditions, implemented by [[negation as failure]], as in the definition:

<syntaxhighlight lang="prolog">
even(0).
even(s(X)) :- not(even(X)).
</syntaxhighlight>