Examples
Datatypes
The most important basic example of a datatype that can be defined by mutual recursion is aComputer functions
Just as algorithms on recursive datatypes 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, andBasic 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. In C:is_even
. In that case, is_odd
, which could be inlined, would call is_even
, but is_even
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:
Advanced examples
A more complicated example is given byMathematical functions
In mathematics, thePrevalence
Mutual recursion is very common inTerminology
Mutual recursion is also known as indirect recursion, by contrast with direct recursion, where a single function calls itself directly. This is simply a difference of emphasis, not a different notion: "indirect recursion" emphasises an individual function, while "mutual recursion" emphasises the set of functions, and does not single out an individual function. For example, if ''f'' calls itself, that is direct recursion. If instead ''f'' calls ''g'' and then ''g'' calls ''f,'' which in turn calls ''g'' again, from the point of view of ''f'' alone, ''f'' is indirectly recursing, while from the point of view of ''g'' alone, ''g'' is indirectly recursing, while from the point of view of both, ''f'' and ''g'' are mutually recursing on each other. Similarly a set of three or more functions that call each other can be called a set of mutually recursive functions.Conversion to direct recursion
Mathematically, a set of mutually recursive functions areSee also
*References
* * * {{cite book , title=Programming in Haskell , last=Hutton , first=Graham , year=2007 , publisher=Cambridge University Press , isbn=978-0-52169269-4External links