Recursion (computer science): Difference between revisions

Revision as of 12:12, 13 March 2024

Revision as of 13:44, 14 March 2024

Line 842:

</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 [[backward chaining|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 anyevery ''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 know how the clause is used to solve problems. The clause can be used top-down, as in Prolog, to reduce problems to subproblems. Or it can be used [[forward chaining|bottom-up (or [[forward chaining|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 (see [[Algorithm#Algorithm = Logic + Control]]).<ref>{{Cite book

| first1 = Stuart J. | last1 = Russell | author1-link = Stuart J. Russell

| first2 = Peter. | last2 = Norvig | author2-link = Peter Norvig