Mutual recursion

In mathematics and computer science, mutual recursion is a form of recursion where two mathematical or computational functions are defined in terms of each other.^[1] It is sometimes called indirect recursion.

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

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:^[2]

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.

Example

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

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

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

These functions are based on the realization that the question is 3 even? is equivalent to is 2 odd?, which is equivalent to is 1 even?, which is equivalent to is 0 odd?; and the answer to that is defined as false. The abs function ensures that number is positive, so that subtracting 1 every time is guaranteed to lead towards 0, not away from it.

Conversion to direct recursion

Any mutual recursion can be converted to direct recursion by inlining the code of one procedure into the other.^[3]

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.^[4] 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

• Recursion (computer science)

References

1. 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.
2. Solving Every Sudoku Puzzle
3. 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)
4. 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)

External links

• Mutual recursion at Rosetta Code