Programmer en langage C
110
© Éditions Eyrolles
8.4 Le cas des fonctions récursives
Le langage C autorise la récursivité des appels de fonctions. Celle-ci peut prendre deux aspects :
●
récursivité directe : une fonction comporte, dans sa définition, au moins un appel à elle-même,
●
récursivité croisée : l’appel d’une fonction entraîne celui d’une autre fonction qui, à son tour,
appelle la fonction initiale (le cycle pouvant d’ailleurs faire intervenir plus de deux fonctions).
Voici un exemple fort classique (d’ailleurs inefficace sur le plan du temps d’exécution) d’une
fonction calculant une factorielle de manière récursive :
Il faut bien voir qu’alors chaque appel de fac entraîne une allocation d’espace pour les variables locales et pour son argument n (apparemment, fct ne comporte aucune variable locale ;
en réalité, il lui faut prévoir un emplacement destiné à recevoir sa valeur de retour). Or chaque
nouvel appel de fac,à l’intérieur de fac, provoque une telle allocation, sans que les emplacements précédents soient libérés.
Il y a donc un empilement des espaces alloués aux variables locales, parallèlement à un empilement des appels de la fonction. Ce n’est que lors de l’exécution de la première instruction
return que l’on commencera à « dépiler » les appels et les emplacements et donc à libérer de
l’espace mémoire.
9 La compilation séparée et ses conséquences
Si le langage C est effectivement un langage que l’on peut qualifier d’opérationnel, c’est en
partie grâce à ses possibilités dites de compilation séparée. En C, en effet, il est possible de
compiler séparément plusieurs programmes (fichiers) source et de rassembler les modules
objet correspondants au moment de l’édition de liens. D’ailleurs, dans certains environnements de programmation, la notion de projet permet de gérer la multiplicité des fichiers
(source et modules objet) pouvant intervenir dans la création d’un programme exécutable.
Cette notion de projet fait intervenir précisément les fichiers à considérer ; généralement, il est
possible de demander de créer le programme exécutable, en ne recompilant que les sources
ayant subi une modification depuis leur dernière compilation.
Indépendamment de ces aspects techniques liés à l’environnement de programmation considéré,
les possibilités de compilation séparée ont une incidence importante au niveau de la portée des
variables globales. C’est cet aspect que nous nous proposons d’étudier maintenant. Dans le
Fonction récursive de calcul de factorielle
long fac (int n)
{
if (n>1) return (fac(n-1)*n) ;
else return(1) ;
}
Delannoy Livre.book Page 110 Mercredi, 6. mai 2009 4:26 16
110
© Éditions Eyrolles
8.4 Le cas des fonctions récursives
Le langage C autorise la récursivité des appels de fonctions. Celle-ci peut prendre deux aspects :
●
récursivité directe : une fonction comporte, dans sa définition, au moins un appel à elle-même,
●
récursivité croisée : l’appel d’une fonction entraîne celui d’une autre fonction qui, à son tour,
appelle la fonction initiale (le cycle pouvant d’ailleurs faire intervenir plus de deux fonctions).
Voici un exemple fort classique (d’ailleurs inefficace sur le plan du temps d’exécution) d’une
fonction calculant une factorielle de manière récursive :
Il faut bien voir qu’alors chaque appel de fac entraîne une allocation d’espace pour les variables locales et pour son argument n (apparemment, fct ne comporte aucune variable locale ;
en réalité, il lui faut prévoir un emplacement destiné à recevoir sa valeur de retour). Or chaque
nouvel appel de fac,à l’intérieur de fac, provoque une telle allocation, sans que les emplacements précédents soient libérés.
Il y a donc un empilement des espaces alloués aux variables locales, parallèlement à un empilement des appels de la fonction. Ce n’est que lors de l’exécution de la première instruction
return que l’on commencera à « dépiler » les appels et les emplacements et donc à libérer de
l’espace mémoire.
9 La compilation séparée et ses conséquences
Si le langage C est effectivement un langage que l’on peut qualifier d’opérationnel, c’est en
partie grâce à ses possibilités dites de compilation séparée. En C, en effet, il est possible de
compiler séparément plusieurs programmes (fichiers) source et de rassembler les modules
objet correspondants au moment de l’édition de liens. D’ailleurs, dans certains environnements de programmation, la notion de projet permet de gérer la multiplicité des fichiers
(source et modules objet) pouvant intervenir dans la création d’un programme exécutable.
Cette notion de projet fait intervenir précisément les fichiers à considérer ; généralement, il est
possible de demander de créer le programme exécutable, en ne recompilant que les sources
ayant subi une modification depuis leur dernière compilation.
Indépendamment de ces aspects techniques liés à l’environnement de programmation considéré,
les possibilités de compilation séparée ont une incidence importante au niveau de la portée des
variables globales. C’est cet aspect que nous nous proposons d’étudier maintenant. Dans le
Fonction récursive de calcul de factorielle
long fac (int n)
{
if (n>1) return (fac(n-1)*n) ;
else return(1) ;
}
Delannoy Livre.book Page 110 Mercredi, 6. mai 2009 4:26 16