Mutual recursion: Difference between revisions

Revision as of 08:40, 10 June 2015

Revision as of 17:11, 10 October 2015

Line 23:

Just as algorithms on recursive data types can naturally be given by recursive functions, algorithms on mutually recursive data structures can be naturally given by mutually recursive functions. Common examples include algorithms on trees, and [[recursive descent parser]]s. As with direct recursion, [[tail call optimization]] is necessary if the recursion depth is large or unbounded, such as using mutual recursion for multitasking. Note that tail call optimization in general (when the function called is not the same as the original function, as in tail-recursive calls) may be more difficult to implement than the special case of tail-recursive call optimization, and thus efficient implementation of mutual tail recursion may be absent from languages that only optimize tail-recursive calls. In languages such as [[Pascal (programming language)|Pascal]] that require declaration before use, mutually recursive functions require [[forward declaration]], as a forward reference cannot be avoided when defining them.

As with directly recursive functions, a [[Recursion (computer science)#Wrapper function|wrapper function]] may be useful, with the mutually recursive functions defined as [[nested function]]s within its scope if this is supported. This is particularly useful for sharing state across a set of functions without having to pass parameters between them.

====Basic examples====