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

Cours 13.2. Profondeur des fonctions récursives

Profondeur

La profondeur correspond au nombre d'appels de la fonction. Une fonction traditionnelle (non récursive) aura une profondeur de 1. Une fonction ayant une profondeur de 5 signifie qu'elle s'est appelée elle-même 4 fois et a été appelée de l'extérieur une fois (que l'on appellera l'appel principal). La profondeur n'est généralement pas une propriété intrinsèque à la fonction mais dépend des paramètres qui lui sont passés.

Limite de profondeur

Afin d'éviter des profondeurs infinies, une fonction récursive doit nécessairement comporter un test d'arrêt qui met un terme à la récursivité. Lorsque le test d'arrêt est vrai, on exécute la récursion terminale qui est l'action réalisée lors du dernier appel de la fonction. Sans cette condition d'arrêt, les appels vont se perpétrer jusqu'à atteindre la limite du nombre d'appel ou jusqu'à saturation de la mémoire. Voici la structure préconisée pour une fonction récursive:

... Fct (...) {
  if (Test) {
    ...         // Récursion terminale (pas d'appel récursif)
  }
  else {
    ...
    Fct (...);  // Appel récursif de la fonction
    ...
  }
}

Exemple

Prenons l'exemple de la fonction factorielle() qui calcule la factorielle d'un entier. L'exemple ci-dessous compte et affiche les appels de la fonction factorielle().

Exercices

Exercice 1

On fournit la fonction récursive power() qui calcule la puissance de deux nombres (\(a^n\)) en s'appuyant sur la relation suivante :

$$ a^n = a \times a^{n-1} $$

double power (double a, int n) {
  if (n==0) return 1;
  return a*power(a,n-1);
}

Mesurer la profondeur lors du calcul de \( 2^{16} \)

2^16 = 65536.00

Exercice 2

On fournit la fonction récursive power() qui calcule la puissance de deux nombres (\(a^n\)) en s'appuyant sur la relation suivante :

$$ a^n = a^{ \dfrac{n}{2} } \times a^{ \dfrac{n}{2} } $$

double power (double a, int n) {

  double R;
  if (n==0) return 1.0;
  R=Puissance2 (a,n/2);
  if (n%2==0) return R*R;
  return a*R*R;
}

Mesurer la profondeur lors du calcul de \( 2^{16} \)

2^16 = 65536.00

Exercice 3

La suite de Fibonacci se définit comme suit pour \(n>1\) :

Valeurs initiales :

$$ f_0 = 0 $$ $$ f_1 = 1 $$

Définition :

$$ f_n = f_{n-1} + f_{n-2} $$

Écrire une fonction qui permet de calculer le nombre de Fibonacci d'ordre n. Nous supposerons que n>1 lors de l'appel principal. Mesurer la profondeur pour n=20. Qu'en conCluez-vous ?

Fibonacci(20) = 6765

Quiz

Qu'est-ce que la profondeur d'une fonction récursive ?

Vérifier Bravo ! Essaie encore ...

Une fonction récursive doit-elle contenir un test ?

Vérifier Bravo ! Essaie encore ...

La récursion terminale ...

Vérifier Bravo ! Essaie encore ...

Voir aussi


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