Talk:Mutual recursion
| This article is rated B-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||
| |||||||||||||||
Use ALL the languages
[edit ]The examples in this article are a little hectic - we start at Standard ML, then go to C (which isn't syntactically valid, functions must have { and }, not to mention bool is more characteristic of C++ and must be explicitly included or defined in C), then swing by Python (which isn't marked as such), back to Standard ML, and finally we end with Scheme. Shouldn't this be simplified to a smaller number of consistent pseudocode examples (that both academics and programmers can understand), instead of a handful of examples in different languages that all say the same thing? Or at the very least, can we pick one language and stick with it? 74.103.134.250 (talk) 21:26, 11 May 2013 (UTC) [reply ]
Tree vs Forest example is not great
[edit ]The tree vs forest example doesn't make sense. A tree is not the "parent" of a "forest" in a real sense. Perhaps a more appropriate parent-child example could be found?
Incorrect statement that all mutual recursion can be converted to direct recursion
[edit ]The second paragraph in the Conversion to direct recursion section says "Any mutual recursion between two procedures can be converted to direct recursion by inlining the code of one procedure into the other." To support this statement, it cites the paper On the conversion of indirect to direct recursion. However, the content of this paper directly contradicts this statement. Section 3 says:
It turns out that we cannot always eliminate all mutual recursion, whether cv-inlining or ov-inlining is used. The following question is the main focus of this article. Question 1. When can we eliminate all mutual recursion?
And Lemma 2 says:
If the call graph contains at least two node-disjoint circuits in an SCC, then there is no mutual-recursion elimination sequence, regardless of whether cv- or ov-inlining is performed.
Lemma 2 contradicts this article's statement that any mutual recursion between two procedures can be converted to direct recursion by inlining. Consider two procedures A and B which each call themselves and also call each other. Neither one can be inlined into the other, since it contains a call to itself.
Proposal: change the incorrect sentence to "Mutual recursion between two procedures can in some cases be converted to direct recursion by inlining the code of one procedure into the other."