Content deleted Content added
m Task 18 (cosmetic): eval 5 templates: hyphenate params (3×); del |ref=harv (2×); |
Dokidaki-ylc (talk | contribs) mNo edit summary |
||
Line 27:
====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 by 1 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:
<syntaxhighlight lang=C>
bool is_even(unsigned int n) {
Line 44:
</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.<ref>"[http://www.cs.bu.edu/~hwxi/ATS/DOCUMENT/TUTORIALATS/HTML/c244.html Mutual Tail-Recursion]" and "[http://www.cs.bu.edu/~hwxi/ATS/TUTORIAL/contents/tail-recursive-functions.html Tail-Recursive Functions]", ''[http://www.cs.bu.edu/~hwxi/ATS/DOCUMENT/TUTORIALATS/HTML/book1.html A Tutorial on Programming Features in ATS],'' Hongwei Xi, 2010</ref> This could be reduced to a single recursive function <code>is_even</code>. In that case, <code>is_odd</code>, which could be inlined, would call <code>is_even</code>, but <code>is_even</code> would only call itself.
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:
| |||