Les fonctions et la pile

Une fonction sert d'abord à ne pas écrire deux fois la même chose, et cette raison suffirait. Mais en C, elle fait quelque chose de plus visible qu'ailleurs : elle réserve un morceau de mémoire à son entrée, et elle le rend à sa sortie. Ce morceau porte un nom, le cadre, et la zone où les cadres s'empilent porte celui de pile.

Ce mécanisme explique trois choses d'un coup : pourquoi une fonction ne peut pas modifier la variable qu'on lui passe, pourquoi une variable locale n'existe plus après le retour, et pourquoi une récursion trop profonde finit par tout arrêter. Le relevé « pile max » sous chaque programme de ces pages donne le creux atteint, en octets.

Une fonction, et ce qu'elle rend

Trois éléments définissent une fonction, et l'ordre compte : le type de ce qu'elle rend, son nom, puis ses paramètres avec leur type. void à la place du type de retour signifie qu'elle ne rend rien, et son return s'écrit alors sans valeur, ou s'omet.

Une fonction déclarée après son appel

Dans un vrai programme C, une fonction employée avant d'être définie doit avoir été déclarée plus haut par son prototype, c'est-à-dire sa première ligne suivie d'un point-virgule : int carre(int n);.
Les fichiers d'en-tête, ceux qu'on inclut avec #include, ne contiennent presque rien d'autre que des prototypes. L'interpréteur de ces pages lit tout le fichier avant d'exécuter, donc il se passe de cette déclaration, mais un compilateur ne le ferait pas.

Le cadre, et ce qu'il devient

À chaque appel, la fonction reçoit sur la pile un espace pour ses paramètres et ses variables locales. Cet espace est rendu au retour, entièrement, sans rien conserver.

La variable total du premier appel et celle du second n'ont aucun rapport : ce sont deux cases différentes, à des instants différents, qui se trouvent occuper la même adresse parce que la première a été rendue avant que la seconde ne soit prise.

Portée et durée de vie

La portée dit d'où un nom est visible : à l'intérieur des accolades où il est déclaré, et nulle part ailleurs.
La durée de vie dit quand la case existe : de l'entrée dans le bloc jusqu'à sa sortie, pour une variable locale.
Les deux coïncident presque toujours, et le presque est ce qui produit les bogues les plus longs à trouver : une adresse qui sort de la fonction survit à la case qu'elle désigne. Ce cas revient au chapitre sur les pointeurs.

Un paramètre est une copie

C'est la règle du langage, sans exception : la valeur de l'appelant est recopiée dans le cadre de la fonction appelée. Ce que la fonction modifie est sa copie.

La fonction affiche 42, main affiche 21, et aucun des deux ne se trompe. Une fonction qui doit modifier une variable de l'appelant ne peut pas le faire en recevant sa valeur : il lui faut son adresse, ce qui est exactement ce à quoi servent les pointeurs.

À manipuler

Dans le bloc ci-dessus, ajouter return n; à la fin de double_valeur, remplacer void par int, et écrire mesure = double_valeur(mesure); dans le main. La valeur change enfin, parce qu'elle a été rendue et réaffectée.
C'est la seule façon de faire sortir un résultat d'une fonction tant que les pointeurs ne sont pas connus, et c'est souvent la meilleure même après.

Ce que coûte une récursion

Une fonction peut s'appeler elle-même. Chaque appel prend son propre cadre, et tous coexistent tant que le plus profond n'est pas revenu.

À manipuler

Exécuter le bloc, puis lire le relevé « pile max » sous la sortie : c'est le creux atteint par la pile, donc la place qu'a demandée la plus profonde des chaînes d'appels.
Remplacer ensuite somme_jusqua(200) par somme_jusqua(2000), relancer, et comparer le relevé. Le résultat reste juste, et la pile a été dix fois plus creusée. Monter encore finit par la faire rejoindre le tas, et l'interpréteur le dit alors au lieu de laisser le programme écraser autre chose.

Remplacer cette récursion par une boucle donne le même résultat pour un cadre unique :

Une récursion sans cas d'arrêt ne s'arrête pas non plus

La condition qui rend sans se rappeler s'appelle le cas de base. Une récursion qui l'oublie, ou dont les appels ne s'en rapprochent pas, empile des cadres jusqu'à ce que la pile rejoigne le tas.
Le message est alors le même pour tout le monde : la pile est pleine. Il ne dit pas quelle fonction est en cause, parce qu'à ce moment-là elles y sont toutes.

À calculer soi-même

Le coût d'un appel se compte en octets, et il se prévoit.

Ce que la pile porte

1.
Une fonction a un paramètre int et deux variables locales int. Combien d'octets son cadre demande-t-il, au minimum ?
2.
Cette même fonction appelée récursivement 100 fois de suite : combien d'octets la pile porte-t-elle au plus creux ?
3.
La pile de cet interpréteur va de l'adresse 65536 jusqu'au tas, qui commence à 4096. Combien d'octets peut-elle porter au maximum ?
4.
Avec des cadres de 12 octets, combien d'appels imbriqués cette pile peut-elle porter ?
5.
Une fonction qui recopie un tableau de 1000 int dans une variable locale : combien d'octets son cadre demande-t-il ?
6.
Combien d'appels imbriqués de cette fonction-là la pile porte-t-elle ?

Les deux derniers résultats disent tout de la pile : elle n'est pas grande, et une seule variable locale volumineuse suffit à réduire la profondeur d'appel à une quinzaine de niveaux.

Vérification

Vérification rapideon peut se reprendre

1.Que devient la variable de l'appelant quand la fonction modifie son paramètre ?

2.Quand le cadre d'une fonction est-il rendu ?

3.Deux appels successifs de la même fonction : leurs variables locales sont-elles liées ?

4.Qu'est-ce qui limite la profondeur d'une récursion ?

5.À quoi sert un prototype, écrit avant la définition ?

Exercices type

Pourquoi une fonction ne peut-elle pas rendre deux valeurs ?

Parce que return rend une seule valeur, de l'unique type déclaré. C'est une limite du langage, et elle a trois contournements.

Passer les adresses des variables à remplir, ce qui est la solution habituelle et qui demande les pointeurs. Grouper les valeurs dans une structure, et rendre la structure. Ou rendre la valeur principale, et signaler par le code de retour si le calcul a réussi.

Le troisième est celui qu'emploie presque toute la bibliothèque standard : un entier qui dit si l'opération s'est bien passée, et le résultat écrit à une adresse fournie.

Quand vaut-il mieux écrire une boucle qu'une récursion ?

Quand le calcul avance d'un pas à la fois sur une seule suite de valeurs : une somme, un parcours de tableau, une recherche linéaire. La boucle occupe un cadre, la récursion en occupe autant que de tours.

La récursion redevient le bon choix quand la structure elle-même se ramifie : un arbre, un dossier qui contient des dossiers, un tri qui coupe le problème en deux. Écrire ces cas-là avec une boucle demande de gérer soi-même une pile de travail, c'est-à-dire de refaire à la main ce que la pile d'appels fait gratuitement.

Un programme embarqué dispose de 8 kibioctets de pile. Une fonction dont le cadre pèse 200 octets peut-elle s'appeler récursivement 50 fois ?

Cinquante cadres de 200 octets demandent 10 000 octets, et 8 kibioctets en font 8 192. La réponse est non, et le dépassement ne produira pas de message : sur une carte sans système d'exploitation, la pile écrasera simplement ce qui se trouve en dessous.

Le calcul se fait avant d'écrire le programme. C'est aussi la raison pour laquelle la récursion est souvent proscrite dans le logiciel embarqué critique : non parce qu'elle est lente, mais parce que sa consommation de pile ne se lit pas dans le texte du programme.

La méthode

Déclarer le type de retour d'abord, et vérifier que tous les chemins rendent bien une valeur.
Considérer chaque paramètre comme une copie, et se demander ce qui doit sortir de la fonction.
Faire sortir les résultats par return tant que les pointeurs ne sont pas nécessaires.
Compter le cadre avant d'écrire une récursion : taille des locales multipliée par la profondeur attendue.
Chercher le cas de base en premier dans une fonction récursive, avant d'écrire l'appel.

Synthèse

Une fonction se définit par un type de retour, un nom et des paramètres typés. void signifie qu'elle ne rend rien.
Chaque appel prend un cadre sur la pile, rendu entièrement au retour.
Les paramètres sont des copies : une fonction ne modifie pas la variable de l'appelant.
Portée et durée de vie se distinguent : le nom cesse d'être visible à la fermeture du bloc, et la case cesse d'exister au même moment.
La profondeur d'une récursion est bornée par la taille de la pile divisée par celle d'un cadre, et une variable locale volumineuse fait chuter cette profondeur.

Et ensuite

Une fonction ne peut pas modifier ce qu'on lui passe, et une variable locale disparaît à son retour. Les deux limites ont la même levée : travailler sur des adresses plutôt que sur des copies. Les tableaux commencent par l'objet qui, en C, est déjà une adresse sans le dire.