Content deleted Content added
m Bot: Migrating 2 langlinks to WP:Wikidata - d:q3454656 |
elaborate substantially |
||
Line 1:
In [[mathematics]] and [[computer science]], '''mutual recursion''' is a form of [[recursion]] where two mathematical or computational objects, such as functions or data types, are defined in terms of each other.<ref>Manuel Rubio-Sánchez, Jaime Urquiza-Fuentes,Cristóbal Pareja-Flores (2002), 'A Gentle Introduction to Mutual Recursion', Proceedings of the 13th annual conference on Innovation and technology in computer science education, June 30–July 2, 2008, Madrid, Spain.</ref> Mutual
==Examples==
In mathematics, the [[Hofstadter sequence#Hofstadter Female and Male sequences|Hofstadter Female and Male sequences]] are an example of a pair of integer sequences defined in a mutually recursive manner.▼
===Data types===
The most important basic example of a data type that can be defined by mutual recursion is a [[tree (data structure)|tree]], which can be defined mutually recursively in terms of a forest (a list of trees). Symbolically:
f: <nowiki>[t[1], ..., t[k]]</nowiki>
t: v f
A forest ''f'' consists of a list of trees, while a tree ''t'' consists of a pair of a value ''v'' and a forest ''f'' (its children). This definition is elegant and easy to work with abstractly (such as when proving theorems about properties of trees), as it expresses a tree in simple terms: a list of one type, and a pair of two types.
This mutually recursive definition can be converted to a singly recursive definition by inlining the definition of a forest:
Mutual recursion is very common in the [[functional programming]] style, and is often used for programs written in [[Lisp programming language|LISP]], [[Scheme (programming language)|Scheme]], [[ML programming language|ML]], and similar [[programming language|languages]]. In languages such as [[Prolog programming language|Prolog]], mutual recursion is almost unavoidable. Some programming styles discourage mutual recursion, claiming that it can be confusing to distinguish the conditions which will return an answer from the conditions that would allow the code to run forever without producing an answer. [[Peter Norvig]] points to a [[design pattern]] which discourages the use entirely, stating:<ref>[http://norvig.com/sudoku.html Solving Every Sudoku Puzzle]</ref>▼
t: v <nowiki>[t[1], ..., t[k]]</nowiki>
A tree ''t'' consists of a pair of a value ''v'' and a list of trees (its children). This definition is more compact, but somewhat messier: a tree consists of a pair of one type and a list another, which require disentangling to prove results about.
===Computer functions===
Just as algorithms on recursive data types can naturally be given by recursive functions, algorithms on mutually recursive data structures can be naturally given by mutually recursive functions. Common examples include algorithms on trees, and [[recursive descent parser]]s.
For example, an algorithm on a tree can be decomposed into its behavior on a value and its behavior on children, and can be split up into two mutually recursive functions, one specifying the behavior on a tree, calling the forest function for the forest of children, and one specifying the behavior on a forest, calling the tree function for the tree in the forest:
<source lang=python>
def f_tree(tree):
f_value(tree.value)
f_forest(tree.children)
def f_forest(forest):
for tree in forest:
f_tree(tree)
</source>
This example easily reduces to a single recursive function by inlining the forest function in the tree function, which is commonly done in practice.
A more complicated example is given by [[recursive descent parser]]s, which can be naturally implemented by having one procedure for each production rule of a grammar, which then mutually recurse.
===Mathematical functions===
▲In mathematics, the [[
Fractals can be computed (up to a given resolution) by recursive functions. This can sometimes be done more elegantly via mutually recursive functions; the [[Sierpiński curve]] is a good example.
==Prevalence==
Mutual recursion is very common in the [[functional programming]] style, and is often used for programs written in [[Lisp programming language|LISP]], [[Scheme (programming language)|Scheme]], [[ML programming language|ML]], and similar [[programming language|languages]]. In languages such as [[Prolog programming language|Prolog]], mutual recursion is almost unavoidable.
▲
{{quote|text=If you have two mutually-recursive functions that both alter the state of an object, try to move almost all the functionality into just one of the functions. Otherwise you will probably end up duplicating code.}}
==Terminology==
Mutual recursion is also known as [[indirect recursion]], by contrast with [[direct recursion]], where a single function calls itself directly. This is simply a difference of emphasis, not a different notion: "indirect recursion" emphasises an individual function, while "mutual recursion" emphasises the set of functions, and does not single out an individual function. For example, if ''f'' calls itself, that is direct recursion. If instead ''f'' calls ''g'' and then ''g'' calls ''f,'' which in turn calls ''g'' again, from the point of view of ''f'' alone, ''f'' is indirectly recursing, while from the point of view of ''g'' alone, ''g'' is indirectly recursing, while from the point of view of both, ''f'' and ''g'' are mutually recursing on each other. Similarly a set of three or more functions that call each other can be called a set of mutually recursive functions.
== Example ==
| |||