Content deleted Content added
m space in book title |
m Task 70: Update syntaxhighlight tags - remove use of deprecated <source> tags |
||
Line 16:
In [[Standard ML]], the tree and forest data types can be mutually recursively defined as follows, allowing empty trees:{{sfn|Harper|2000|loc="[https://www.cs.cmu.edu/~rwh/introsml/core/datatypes.htm Date Types]"}}
<
datatype 'a tree = Empty | Node of 'a * 'a forest
and 'a forest = Nil | Cons of 'a tree * 'a forest
</syntaxhighlight>
===Computer functions===
Line 28:
====Basic examples====
A standard example of mutual recursion, which is admittedly artificial, determines whether a non-negative number is even or odd by defining two separate functions that call each other, decrementing each time.{{sfn|Hutton|2007|loc=6.5 Mutual recursion, pp. [https://books.google.com/books?id=olp7lAtpRX0C&pg=PA53&dq=%22mutual+recursion%22 53–55]}} In C:
<
bool is_even(unsigned int n) {
if (n == 0)
Line 42:
return is_even(n - 1);
}
</syntaxhighlight>
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. This example is mutual [[single recursion]], and could easily be replaced by iteration. In this example, the mutually recursive calls are [[tail call]]s, and tail call optimization would be necessary to execute in constant stack space. In C, this would take ''O''(''n'') stack space, unless rewritten to use jumps instead of calls.
Line 48:
As a more general class of examples, 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. In Python:
<
def f_tree(tree) -> None:
f_value(tree.value)
Line 56:
for tree in forest:
f_tree(tree)
</syntaxhighlight>
In this case the tree function calls the forest function by single recursion, but the forest function calls the tree function by [[multiple recursion]].
Using the [[Standard ML]] data type above, the size of a tree (number of nodes) can be computed via the following mutually recursive functions:{{sfn|Harper|2000|loc="[https://www.cs.cmu.edu/~rwh/introsml/core/datatypes.htm Datatypes]"}}
<
fun size_tree Empty = 0
| size_tree (Node (_, f)) = 1 + size_forest f
and size_forest Nil = 0
| size_forest (Cons (t, f')) = size_tree t + size_forest f'
</syntaxhighlight>
A more detailed example in Scheme, counting the leaves of a tree:{{sfn|Harvey|Wright|1999|loc=V. Abstraction: 18. Trees: Mutual Recursion, pp. [https://books.google.com/books?id=igJRhp0KGn8C&pg=PA310&dq=%22mutual%20recursion%22 310–313]}}
<
(define (count-leaves tree)
(if (leaf? tree)
Line 79:
(+ (count-leaves (car forest))
(count-leaves-in-forest (cdr forest)))))
</syntaxhighlight>
These examples reduce easily to a single recursive function by inlining the forest function in the tree function, which is commonly done in practice: directly 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.
| |||