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

Le dernier appel retourne 0 (c'est-à-dire << faux >>) :

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.