Mutual recursion is a form of recursion

Recursion

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...

 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

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...

 style, and is often used for programs written in LISP

Lisp programming language

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...

, Scheme, ML

ML programming language

ML is a general-purpose functional programming language developed by Robin Milner and others in the early 1970s at the University of Edinburgh, whose syntax is inspired by ISWIM...

, and similar languages

Programming language

A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....

. 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. Peter Norvig

Peter Norvig

Peter Norvig is an American computer scientist. He is currently the Director of Research at Google Inc.-Educational Background:...

 points to a design pattern

Design pattern

A design pattern in architecture and computer science is a formal way of documenting a solution to a design problem in a particular field of expertise. The idea was introduced by the architect Christopher Alexander in the field of architecture and has been adapted for various other disciplines,...

 which discourages the use entirely, stating
Any mutual recursion can be converted to direct recursion using procedural inlining.

In mathematics, the Hofstadter Female and Male sequences are an example of a pair of integer sequences defined in a mutually recursive manner.