In mathematics and computer science, mutual recursion is a form of recursion where two mathematical or computational objects, such as functions or data types, are defined in terms of each other.[1] Mutual recursion is very common in functional programming and in some problem domains, such as recursive descent parsers, where the data types are naturally mutually recursive, but is uncommon in other domains.
Examples
Data types
The most important basic example of a data type that can be defined by mutual recursion is a tree, which can be defined mutually recursively in terms of a forest (a list of trees). Symbolically:
f: [t[1], ..., t[k]] t: v f
A forest f consists of a list of trees, while a tree t consists of a pair of a value v and a forest f (its children). This definition is elegant and easy to work with abstractly (such as when proving theorems about properties of trees), as it expresses a tree in simple terms: a list of one type, and a pair of two types.
This mutually recursive definition can be converted to a singly recursive definition by inlining the definition of a forest:
t: v [t[1], ..., t[k]]
A tree t consists of a pair of a value v and a list of trees (its children). This definition is more compact, but somewhat messier: a tree consists of a pair of one type and a list another, which require disentangling to prove results about.
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 parsers.
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.[2] In 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);
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. In this example, the mutually recursive calls are in tail position, and tail call optimization would be necessary for this to execute in constant stack space; in C this would take O(n) stack space. This could be reduced to a single recursive function is_even, with is_odd calling is_even, but is_even only calling itself, with is_odd 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:
def f_tree(tree):
f_value(tree.value)
f_forest(tree.children)
def f_forest(forest):
for tree in forest:
f_tree(tree)
A more detailed example in Scheme, counting the leaves of a tree:[3]
(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)))))
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.
A more complicated example is given by recursive descent parsers, which can be naturally implemented by having one function for each 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.
Mathematical functions
In mathematics, the Hofstadter Female and Male sequences are an example of a pair of integer sequences defined in a mutually recursive manner.
Fractals can be computed (up to a given resolution) by recursive functions. This can sometimes be done more elegantly via mutually recursive functions; the Sierpiński curve is a good example.
Prevalence
Mutual recursion is very common in the functional programming style, and is often used for programs written in LISP, Scheme, ML, and similar languages. In languages such as Prolog, mutual recursion is almost unavoidable.
Some programming styles discourage mutual recursion, claiming that it can be confusing to distinguish the conditions which will return an answer from the conditions that would allow the code to run forever without producing an answer. Peter Norvig points to a design pattern which discourages the use entirely, stating:[4]
If you have two mutually-recursive functions that both alter the state of an object, try to move almost all the functionality into just one of the functions. Otherwise you will probably end up duplicating code.
Terminology
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
Any mutual recursion between two procedures can be converted to direct recursion by inlining the code of one procedure into the other.[5] If there is only one site where one procedure calls the other, this is straightforward, though if there are several it can involve code duplication.
Alternately, any number of procedures can be merged into a single procedure that takes as argument a variant record (or algebraic data type) representing the selection of a procedure and its arguments; the merged procedure then dispatches on its argument to execute the corresponding code and uses direct recursion to call self as appropriate. This can be seen as a limited application of defunctionalization.[6] This translation may be useful when any of the mutually recursive procedures can be called by outside code, so there is no obvious case for inlining one procedure into the other. Such code then needs to be modified so that procedure calls are performed by bundling arguments into a variant record as described; alternately, wrapper procedures may be used for this task.
See also
References
- ^ Manuel Rubio-Sánchez, Jaime Urquiza-Fuentes,Cristóbal Pareja-Flores (2002), 'A Gentle Introduction to Mutual Recursion', Proceedings of the 13th annual conference on Innovation and technology in computer science education, June 30–July 2, 2008, Madrid, Spain.
- ^ Hutton 2007, 6.5 Mutual recursion, pp. 53–55.
- ^ Harvey & Wright 1999, V. Abstraction: 18. Trees: Mutual Recursion, pp. 310–313.
- ^ Solving Every Sudoku Puzzle
- ^ On the Conversion of Indirect to Direct Recursion by Owen Kaser, C. R. Ramakrishnan, and Shaunak Pawagi at State University of New York, Stony Brook (1993)
- ^ Reynolds, John (August, 1972). "Definitional Interpreters for Higher-Order Programming Languages" (PDF). Proceedings of the ACM Annual Conference. Boston, Massachusetts. pp. 717–740.
{{cite conference}}: Check date values in:|date=(help); Unknown parameter|booktitle=ignored (|book-title=suggested) (help)