Mutual recursion is a form of recursion Recursion, in mathematics and computer science, is a method of defining functions in which the function being defined is applied within its own definition. The term is also used more generally to describe a process of repeating objects in a self-similar way. For instance, when the surfaces of two mirrors are almost parallel with each other the where two mathematical or computational functions are defined in terms of each other.
For instance, consider two functions even? and odd? defined as follows:
function even?(number : Integer) if number == 0 then return true else return odd?(abs(number)-1) function odd?(number : Integer) if number == 0 then return false else return even?(abs(number)-1)
These functions are based on the realization that the question is three even is equivalent to the question, is two odd, which is the same as asking if 1 is even or 0 is odd. In the end, the answer is no, as realized by the function odd?. The abs function is used to ensure that number decrements towards zero even when it starts off as a negative value.
Mutual recursion is very common in the functional programming In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state. Functional programming has its roots in the style, and is often used for programs written in LISP Lisp is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older. Like Fortran, Lisp has changed a great deal since its early days, and a number of dialects have, Scheme Scheme is a multi-paradigm programming language. It is one of the two main dialects of Lisp and supports a number of programming paradigms but is best known for its support of functional programming. It was developed by Guy L. Steele and Gerald Jay Sussman in the 1970s. Scheme was introduced to the academic world via a series of papers now, ML ML is a general-purpose functional programming language developed by Robin Milner and others in the late 1970s at the University of Edinburgh, whose syntax is inspired by ISWIM. Historically, ML stands for metalanguage: it was conceived to develop proof tactics in the LCF theorem prover . It is known for its use of the Hindley-Milner type, and similar languages A programming language is an artificial language designed to express computations that can be performed by a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine, to express algorithms precisely, or as a mode of human communication. In languages such as Prolog, mutual recursion is almost unavoidable.
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. It is usually possible to turn two mutually recursive functions into a single recursive function by inlining the code of one into the other, possibly at the expense of legibility.
In mathematics, the Hofstadter Female and Male sequences are an example of a pair of integer sequences defined in a mutually recursive manner.
References
- 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.
See also
Categories: Theory of computation | Recursion theory
Hamlet D'Arcy
hu, 07 Aug 2008 02:06:00 GM
This makes it impossible for any language on the JVM to support tail call folding on functions which are *. mutually. * . recursive. . Since . mutual recursion. is quite common, it's not hard to see why this is a crippling limitation for FP on the ...
