Content deleted Content added
→External links: Stack Overflow |
|||
Line 83:
== 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.▼
▲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)...
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]].<ref>{{cite conference
| |||