FriconiX
Des milliers de pictogrammes gratuits dessinés avec amour!

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);
}

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

Quiz

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

Vérifier Bravo ! Essaie encore ...

Voir aussi


Dernière mise à jour : 07/11/2020