Cours 13.2. Profondeur des fonctions récursives

Profondeur

La profondeur d'une fonction récursive est le nombre de fois que la fonction s'appelle elle-même avant d'atteindre une condition d'arrêt. En général, la profondeur d'une fonction récursive augmente à mesure qu'un paramètre d'entrée de la fonction devient plus grande.

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().

Tester l'exemple en ligne

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

Faire l'exercice

Solution

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=power (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

Faire l'exercice

Solution

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

Faire l'exercice

Solution

Quiz

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

Le nombre de lignes de code dans la fonction

le nombre d'appels de la fonctions uniquement depuis une autre fonction

le nombre d'appels récursifs incluant l'appel principal

le nombre d'appels récursifs sans l'appel principal

Vérifier

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

jamais

toujours

c'est optionnel

c'est obligatoire pour la récursion terminale

Vérifier

La récursion terminale ...

est le premier appel d'une fonction récursive

est le dernier appel d'une fonction récursive

appelle la fonction récursive depuis elle-même

n'appelle plus la fonction récursive

Vérifier

Cours 13.1 Sommaire Cours 13.3

Voir aussi

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