Editing Mutual recursion (section)

====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) {
    if (n == 0)
        return true;
    else
        return is_odd(n - 1);
}

bool is_odd(unsigned int n) {
    if (n == 0)
        return false;
    else
        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.<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:
<syntaxhighlight lang="python">
def f_tree(tree) -> None:
    f_value(tree.value)
    f_forest(tree.children)

def f_forest(forest) -> None:
    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 datatype 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]"}}
<syntaxhighlight lang="sml">
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 (programming language)|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]}}
<syntaxhighlight lang=scheme>
(define (count-leaves tree)
  (if (leaf? tree)
      1
      (count-leaves-in-forest (children tree))))

(define (count-leaves-in-forest forest)
  (if (null? forest)
      0
      (+ (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.