Content deleted Content added
m No need for static |
Recursion in Logic Programming |
||
Line 831:
where {{mvar|a}} represents the number of recursive calls at each level of recursion, {{mvar|b}} represents by what factor smaller the input is for the next level of recursion (i.e. the number of pieces you divide the problem into), and {{math|''f''(''n'')}} represents the work that the function does independently of any recursion (e.g. partitioning, recombining) at each level of recursion.
==Recursion in Logic Programming==
In the procedural interpretation of [[logic programming|logic programs]], clauses (or rules) of the form <syntaxhighlight inline lang="prolog">A :- B</syntaxhighlight> are treated as procedures, which reduce goals of the form <code>A</code> to subgoals of the form <code>B</code>.
For example, the [[Prolog]] clauses:
<syntaxhighlight lang="prolog">
path(X,Y) :- arc(X,Y).
path(X,Y) :- arc(X,Z), path(Z,Y).
</syntaxhighlight>
define a procedure, which can be used to search for a path from X to Y, either by finding a direct arc from X to Y, or by finding an arc from X to Z, and then searching recursively for a path from Z to Y. Prolog executes the procedure by [[backward chaining|reasoning top-down (or backwards)]] and searching the space of possible paths depth-first, one branch at a time. If it tries the second clause, and finitely fails to find a path from Z to Y, it backtracks and tries to find an arc from X to another node, and then searches for a path from that other node to Y.
However, in the logical reading of logic programs, clauses are understood [[declarative program|declaratively]] as universally quantified conditionals. For example, the recursive clause of the path-finding procedure is understood as [[Knowledge representation and reasoning|representing the knowledge]] that, for any X, Y and Z, if there is an arc from X to Z and a path from Z to Y then there is a path from X to Y. In symbolic form:
:<math>\forall X, Y, Z(arc(X,Z)\land path(Z,Y) \rightarrow path(X,Y)).</math>
The logical reading frees the reader from needing to have any knowledge about how the knowledge is used to solve problems. The knowledge can be used top-down, as in Prolog, to reduce problems to subproblems. Or it can be used [[forward chaining|bottom-up (or forwards)]], as in [[Datalog]], to derive conclusions from conditions. This [[separation of concerns]] is a form of [[Abstraction (computer science)|abstraction]], which [[Algorithm#Algorithm = Logic + Control|separates declarative knowledge from problem solving methods]].<ref>{{Cite book
| first1 = Stuart J. | last1 = Russell | author1-link = Stuart J. Russell
| first2 = Peter. | last2 = Norvig | author2-link = Peter Norvig
| title=[[Artificial Intelligence: A Modern Approach]] §9.3, §9.4
| year = 2021
| edition = 4th
| isbn = 978-0134610993
| lccn = 20190474
| publisher = Pearson | ___location = Hoboken
}}</ref>
==See also==
Line 844 ⟶ 871:
* [[Primitive recursive function]]s
* [[Tak (function)]]
* [[Logic programming]]
==Notes==
| |||