Mutual recursion: Difference between revisions

Revision as of 01:56, 3 August 2016

Revision as of 14:05, 1 September 2016

Line 26:

====Basic examples====

A standard example of mutual recursion, which is admittedly artificial, is determiningdetermines whether a non-negative number is even or is odd by havingdefining two separate functions andthat callingcall 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:

<source lang=C>

bool is_even(unsigned int n) {

Line 43:

</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. 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 for this to execute in constant stack space;. inIn 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>,. withIn that case, <code>is_odd</code>, callingwhich could be inlined, would call <code>is_even</code>, but <code>is_even</code> would only callingcall itself, with <code>is_odd</code> inlined.

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: