Récursivité mutuelle

Plus généralement, un ensemble de définitions est mutuellement récursif si la relation << $f$ appelle $g$ >> admet un cycle : $f_1$ appelle ...appelle $f_n$ appelle $f_1$. L'exemple suivant est classique (et sans grand intérêt) :

bool pair(int n);

bool impair(int n) {
  if (n == 0) {
    return false;
  } else {
    return pair(n-1);
  }
}

bool pair(int n) {
  if (n == 0) {
    return true;
  } else {
    return impair(n-1);
  }
}

Les fonctions pair et impair s'appellent mutuellement :

$$\mathtt{pair}(3) \to \mathtt{impair}(2) \to \mathtt{pair}(1) \to \mathtt{impair}(0)$$

Le dernier appel retourne false :

$$\mathtt{impair}(0) \stackrel{\mathtt{false}}{\to} \mathtt{p... ...mathtt{pair}(3) \stackrel{\mathtt{false}}{\to} \texttt{main()}$$

La définition de la première fonction doit être précédée de la déclaration de la seconde fonction : tout nom doit être déclaré avant d'être utilisé. Les définitions mutuellement récursives sont surtout utiles pour travailler sur des structures de données mutuellement récursives.