Cours 13.3. Récursion croisée

Récursivité croisée

La récursivité croisée (ou récursion mutuelle) traduit le fait que deux fonctions s'appellent mutuellement. Une fonction f1() effectue un calcul en appelant une fonction f2(), qui elle-même appelle la fonction f1(). Le risque est que les conditions d'arrêt ne soient jamais vraie et que la limite de profondeur soit atteinte.

Exemple

Voici un exemple de fonctions pair() et impair() qui vérifie la parité d'un entier n avec une récursivité croisée. C'est exemple n'est clairement pas optimal, il s'agit juste d'une illustration :

// Retourne 1 si n est pair
char pair(int n) {
  if (n==0) return 1;
  return impair(n-1);
}

// Retourne 1 si n est impair
char impair(int n) {
  if (n==0) return 0;
  return pair(n-1);
}

Tester l'exemple en ligne

Exercice

Ecrire sous forme récursives les fonctions $u_n$ et $v_n$ conformément à la description suivante:

Valeurs initiales :

$$ u_0=1 $$ $$ v_0=2 $$

Définition :

$$ u_n = 3.u_{n-1} + 2.v_{n-1} $$ $$ v_n = 2.u_{n-1} + 3.v_{n-1} $$

Voici l'affichage escompté du programme :

u(0) = 1     v(0)=2
u(1) = 7     v(1)=8
u(2) = 37    v(2)=38
u(3) = 187   v(3)=188
u(4) = 937   v(4)=938

Faire l'exercice

Solution

Quiz

Quand est-on dans une récursion croisée ?

quand une fonction s'appelle elle-même

quand deux fonctions s'appellent entre-elles

quand trois fonctions s'appellent entre-elles

quand deux ou plus fonctions s'appellent entre-elles

Vérifier

Cours 13.2 Sommaire Cours 14.1

Voir aussi

Dernière mise à jour : 06/12/2022