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]
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.
- ^ 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)