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₁ appelle ...appelle f_n appelle f₁.   L'exemple suivant est classique (et sans grand intérêt) :

int pair(int n);

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

int pair(int n) {
  if (n == 0) {
    return 1;
  } 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 0 (c'est-à-dire << faux >>) :

$$\mathtt{impair}(0) \stackrel{0}{\to} \mathtt{pair}(1) \stac... ...el{0}{\to} \mathtt{pair}(3) \stackrel{0}{\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.