Lors de mes pérégrinations geekesques, j’ai pu entendre dansquelques contrées universitaires, que les compilateurs C/C++ savaient optimiserles fonctions récursives. Certains disaient qu’elles étaient transformé enboucles itérative d’autres disaient que si elles étaient écrites correctementelles devenaient récursives terminales.
Qu’est-ce qu’une fonction récursive correctementécrite ?
int fonction_recursive(int parametre){
if(parametre==0){
return parametre;
}
else
{
int tmp=parametre- 1;
return fonction_recursive(tmp);
}
}
C’est une fonction qui retourne uniquement un appel de fonction.
Ce que j’appelle une fonction récursive non correctement écrite c’est :
int fonction_recursive(int parametre){
if(parametre==0){
return parametre;
}
else
{
int tmp=parametre- 1;
returntmp + fonction_recursive(tmp);
}
}
Ici le return contient un appel de fonction plus uneopération. On m’a dit que ce type de fonction n’est pas optimisable par lecompilateur car pour mémoriser la variable tmp, le compilateur devra la placersur la pile. La pile grossira a chaque appel de fonction, ce qui nuira auxperformances, de plus à partir d’un certain nombre d’appels on se trouveconfronté a un stack overflow. On m’a dit aussi que certains compilateurs commeGCC sont capable d’optimiser les fonctions récursives correctement écrites.J’entends par optimisation effectuer les appels récursifs sans faire grossir lapile (vu qu’aucune variable n’a besoin d’être mémorisé) et donc sans aller audevant de quelques déconvenues (stack overflow…).
Ne sachant pas si le compilateur C/C++ de visual studio 2008pouvait en faire autant j’ai décidé de mener une expérience. Deuxcompilateurs : GCC 3.4.5 (mingw) et le VC++ 2008 le tout sous Windows.
Sur les deux plateformes la fonction correctement écrite estoptimisé, petit bémol VC++ (contrairement à GCC) n’est pas capable d’optimiser les fonctionset de générer des informations de débogage. Du coup on ne peut pas voir avec ledébogueur si la pile grossit ou pas. Pour s’avoir si l’optimisation était passéej’ai du passé en paramètre à la fonction un argument de très grande valeur.Cette valeur provoquait un stack overflow sans optimisation. Avecl’optimisation la fonction se terminait sans erreur.
La fonction non correctement écrite est (à ma grandesurprise) optimisé par VC++ mais pas par GCC (expérience à renouveler avec GCC4.3), la encore seule un argument de très grande valeur m’a permis de vérifierque l’optimisation a été bien effectuée.
Aucun commentaire:
Enregistrer un commentaire