Content deleted Content added
→References: {cite isbn} |
→Computer functions: more examples |
||
Line 13:
===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. As with direct recursion, [[tail call optimization]] is necessary if the recursion depth is large or unbounded, such as using mutual recursion for multitasking.
====Basic examples====
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:
<source lang=C>
Line 59 ⟶ 60:
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.
====Advanced examples====
A more complicated example is given by [[recursive descent parser]]s, which can be naturally implemented by having one function for each [[Production (computer science)|production rule]] of a grammar, which then mutually recurse. This can also be done without mutual recursion, for example by still having separate functions for each production rule, but having them called by a single controller function, or by putting all the grammar in a single function.
More generally, mutual recursion can implement a [[finite-state machine]], with one function for each state; this requires tail call optimization if the number of state changes is large or unbounded. This can be used as a simple form of [[cooperative multitasking]]. A similar approach to multitasking is to instead use [[coroutine]]s which call each other, where rather than terminating by calling another routine, one coroutine yields to another but does not terminate, and then resumes execution when it is yielded back to. This allows individual coroutines to hold state, without it needing to be passed by parameters or stored in shared variables.
There are also some algorithms which naturally have two phases, such as [[minimax]] (min and max), and these can be implemented by having each phase in a separate function with mutual recursion, though they can also be combined into a single function with direct recursion.
===Mathematical functions===
| |||