Content deleted Content added
elaborate substantially |
move and elaborate examples |
||
Line 15:
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.
A standard example of mutually recursion, which is admittedly artificial, is determining whether a non-negative number is even or is odd by having two separate functions and calling each other, decrementing each time.{{sfn|Hutton|2007|loc=6.5 Mutual recursion, pp. [http://books.google.com/books?id=olp7lAtpRX0C&pg=PA53&dq=%22mutual+recursion%22 53–55]}} In C:
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=C>
bool is_even(unsigned int n)
if (n == 0)
bool is_odd(unsigned int n)
if (n == 0)
</source>
These functions are based on the observation that the question ''is 4 even?'' is equivalent to ''is 3 odd?'', which is in turn equivalent to ''is 2 even?'', and so on down to 0. In this example, the mutually recursive calls are in tail position, and tail call optimization would be necessary for this to execute in constant stack space; in C this would take ''O''(''n'') stack space. This could be reduced to a single recursive function <code>is_even</code>, with <code>is_odd</code> calling <code>is_even</code>, but <code>is_even</code> only calling itself, with <code>is_odd</code> inlined.
▲
<source lang=python>
def f_tree(tree):
Line 26 ⟶ 43:
</source>
A more detailed example in Scheme, counting the leaves of a tree:{{sfn|Harvey|Wright|1999|loc=V. Abstraction: 18. Trees: Mutual Recursion, pp. [http://books.google.co.jp/books?id=igJRhp0KGn8C&pg=PA310&dq=%22mutual%20recursion%22 310–313]}}
<source lang=scheme>
(define (count-leaves tree)
(if (leaf? tree)
1
(count-leaves-in-forest (children tree))))
(define (count-leaves-in-forest forest)
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.▼
(if (null? forest)
0
(+ (count-leaves (car forest))
(count-leaves-in-forest (cdr forest)))))
</source>
These examples reduce easily to a single recursive function by inlining the forest function in the tree function, which is commonly done in practice: simple recursive functions that operate on trees sequentially process the value of the node and recurse on the children within one function, rather than dividing these into two separate functions.
▲A more complicated example is given by [[recursive descent parser]]s, which can be naturally implemented by having one
===Mathematical functions===
Line 43 ⟶ 74:
==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.
▲ '''return''' true
▲ '''else'''
▲ '''return''' odd?(abs(number)-1)
▲ '''return''' false
▲ '''else'''
▲ '''return''' even?(abs(number)-1)
== Conversion to direct recursion ==
Any mutual recursion between two procedures can be converted to direct recursion by inlining the code of one procedure into the other.<ref>[http://delivery.acm.org/10.1145/180000/176510/p151-kaser.pdf?key1=176510&key2=1857140721&coll=GUIDE&dl=GUIDE&CFID=82873082&CFTOKEN=54657523 On the Conversion of Indirect to Direct Recursion] by Owen Kaser, C. R. Ramakrishnan, and Shaunak Pawagi at [[State University of New York, Stony Brook]] (1993)</ref> If there is only one site where one procedure calls the other, this is straightforward, though if there are several it can involve code duplication.
Alternately, any number of procedures can be merged into a single procedure that takes as argument a [[variant record]] (or [[algebraic data type]]) representing the selection of a procedure and its arguments; the merged procedure then dispatches on its argument to execute the corresponding code and uses direct recursion to call self as appropriate. This can be seen as a limited application of [[defunctionalization]].<ref>{{cite conference
Line 74 ⟶ 87:
| pages = 717–740
| url = http://www.brics.dk/~hosc/local/HOSC-11-4-pp363-397.pdf
}}</ref> This translation may be useful when any of the mutually recursive procedures can be called by outside code, so there is no obvious case for inlining one procedure into the other.
== See also ==
| |||