Mutual recursion: Difference between revisions

Revision as of 18:50, 9 February 2013

Revision as of 13:28, 7 March 2013

Line 28:

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>

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

| first = John | last = Reynolds | authorlink = John_C._Reynolds

| title = Definitional Interpreters for Higher-Order Programming Languages

Line 36:

| pages = 717–740

| url = http://www.brics.dk/~hosc/local/HOSC-11-4-pp363-397.pdf

}}</ref>. 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 ==

Line 51:

[[Category:Recursion]]

[[fr:récursionRécursion mutuelle]]

[[ja:相互再帰]]