Mutual recursion: Difference between revisions

Revision as of 14:57, 12 March 2012

Revision as of 15:15, 15 May 2012

Line 1:

In [[mathematics]] and [[computer science]], '''Mutualmutual recursion''' is a form of [[recursion]] where two mathematical or computational functions are defined in terms of each other.<ref>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.</ref>

In mathematics, the [[Hofstadter sequence#Hofstadter Female and Male sequences|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 programming language|LISP]], [[Scheme (programming language)|Scheme]], [[ML programming language|ML]], and similar [[programming language|languages]]. In languages such as [[Prolog programming language|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:<ref>[http://norvig.com/sudoku.html Solving Every Sudoku Puzzle]</ref>

{{quote|text=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.|sign=Peter Norvig <ref>[http://norvig.com/sudoku.html Solving Every Sudoku Puzzle]</ref>}}

== Example ==

For instance, consider two functions <code>even?</code> and <code>odd?</code> defined as follows:

Line 17 ⟶ 24:

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 <code>odd?</code>. The <code>abs</code> function is used to ensure that <code>number</code> decrements towards zero even when it starts off as a negative value.

== Conversion to direct recursion ==

Mutual recursion is very common in the [[functional programming]] style, and is often used for programs written in [[Lisp programming language|LISP]], [[Scheme (programming language)|Scheme]], [[ML programming language|ML]], and similar [[programming language|languages]]. In languages such as [[Prolog programming language|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

{{quote|text=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.|sign=Peter Norvig <ref>[http://norvig.com/sudoku.html Solving Every Sudoku Puzzle]</ref>}}

Any mutual recursion can be converted to direct recursion by inlining the code of one procedure into the other.<ref>[http://delivery.acm.org/10.1145/180000/176510/p151-kaser.pdf?key1=176510&key2=1857140721&coll=GUIDE&dl=GUIDE&CFID=82873082&CFTOKEN=54657523 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)</ref>

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

== See also ==

Line 31 ⟶ 33:

== References ==

{{reflist|2}}

<references />

[[Category:Theory of computation]]