Mutual recursion: Difference between revisions

Revision as of 18:32, 15 January 2022

Latest revision as of 04:28, 15 July 2025

(6 intermediate revisions by 4 users not shown)

Line 1:

{{short description|FormTwo of recursionfunctions defined from each other}}

<!-- [[WP:NFCC]] violation: [[File:DrawingHands.jpg|thumb|upright|"[[Drawing Hands]]", a drawing by [[M. C. Escher]]]] -->

In [[mathematics]] and [[computer science]], '''mutual recursion''' is a form of [[Recursion (computer science)|recursion]] where two or more mathematical or computational objects, such as functions or datatypes, 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> Mutual recursion is very common in [[functional programming]] and in some problem domains, such as [[recursive descent parser]]s, where the datatypes are naturally mutually recursive.

==Examples==

Line 66:

</syntaxhighlight>

A more detailed example in [[Scheme (programming language)|Scheme]], counting the leaves of a tree:{{sfn|Harvey|Wright|1999|loc=V. Abstraction: 18. Trees: Mutual Recursion, pp. [https://books.google.com/books?id=igJRhp0KGn8C&pg=PA310&dq=%22mutual%20recursion%22 310–313]}}

<syntaxhighlight lang=scheme>

(define (count-leaves tree)

Line 98:

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>

{{quoteBlockquote|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.}}

==Terminology==

Line 104:

==Conversion to direct recursion==

Mathematically, a set of mutually recursive functions are [[primitive recursive]], which can be proven by [[course-of-values recursion]],<ref>"[http://planetmath.org/mutualrecursion mutual recursion]", ''PlanetMath''</ref> building a single function ''F'' that lists the values of the individual recursive function in order: <math>F = f_1(0), f_2(0), f_1(1), f_2(1), \dots,</math> and rewriting the mutual recursion as a primitive recursion.

Any mutual recursion between two procedures 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> 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. In terms of the call stack, two mutually recursive procedures yield a stack ABABAB..., and inlining B into A yields the direct recursion (AB)(AB)(AB)...