Mutual recursion

related topics
{math, number, function}
{style, bgcolor, rowspan}
{woman, child, man}

Mutual recursion is a form of recursion where two mathematical or computational functions are defined in terms of each other.[1]

For instance, consider two functions even? and odd? defined as follows:

function even?(number : Integer)
    if number == 0 then
        return true
        return odd?(abs(number)-1)
function odd?(number : Integer)
    if number == 0 then
        return false
        return even?(abs(number)-1)

These functions are based on the realization that the question is three even is equivalent to the question, is two odd, which is the same as asking if 1 is even or 0 is odd. In the end, the answer is no, as realized by the function odd?. The abs function is used to ensure that number decrements towards zero even when it starts off as a negative value.

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. It is usually possible to turn two mutually recursive functions into a single recursive function by inlining the code of one into the other, possibly at the expense of legibility. Peter Norvig points to a design pattern which discourages the use entirely, stating

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.
—Peter Norvig [2]

Any mutual recursion can be converted to direct recursion using procedural inlining.[3]

In mathematics, the Hofstadter Female and Male sequences are an example of a pair of integer sequences defined in a mutually recursive manner.


See also


Full article ▸

related documents
Characteristic subgroup
Baire category theorem
Sophie Germain prime
Complete category
Hamiltonian path problem
Category of sets
Axiom of union
Normal morphism
Elias delta coding
Abelian category
Brun's constant
Column vector
Sum rule in differentiation
Up to
Blum Blum Shub
Contraction mapping
AVL tree
Complete measure
Double precision
LALR parser
Nearest neighbour algorithm
Best-first search
Lyapunov fractal
Inverse functions and differentiation
Lagged Fibonacci generator
Tree structure