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.
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
...
}
}
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()
.
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
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
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
Qu'est-ce que la profondeur d'une fonction récursive ?
Une fonction récursive doit-elle contenir un test ?
La récursion terminale ...