Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Informatique

Fonctions en C : paramètres, portée, pile d'appels et récursivité

Définitions et prototypes, passage par valeur, variables locales, globales et statiques, la pile d'appels, récursivité avec la factorielle et Fibonacci, tests unitaires.

https://www.electronics-engineering.com/fr/fonctions-c-pile-d-appels-recursivite/

Pas encore de vote : soyez le premier à noter cette page.

Un long programme écrit entièrement dans main devient vite illisible. Les fonctions permettent de découper le problème en parties, chacune avec un nom, des paramètres et un résultat, à écrire, tester et réutiliser séparément. Dans cette leçon nous voyons comment on les définit, comment on passe les paramètres, ce qui se passe en mémoire pendant un appel (la pile) et la récursivité.

Définition et appel

#include <stdio.h>

/* prototype: tells the compiler the name, parameters and result type */
double divider(double vin, double r1, double r2);

int main(void)
{
    double vout = divider(12.0, 10e3, 4.7e3);
    printf("Vout = %.2f V\n", vout);         /* Vout = 3.84 V */
    return 0;
}

/* output voltage of a resistive divider */
double divider(double vin, double r1, double r2)
{
    return vin * r2 / (r1 + r2);
}
  • Le prototype avant main permet d’utiliser la fonction avant de la définir. Les prototypes sont en général regroupés dans un fichier d’en-tête .h.
  • Les paramètres formels (vin, r1, r2) sont des variables locales qui reçoivent les valeurs des arguments passés lors de l’appel.
  • return termine la fonction et renvoie la valeur. Une fonction qui ne renvoie rien a le type void.

Le passage par valeur

En C les arguments sont passés par valeur : la fonction reçoit une copie, et la modifier ne change pas la variable de l’appelant.

void twice(int x) { x = 2 * x; }      /* changes only the local copy */

int main(void)
{
    int n = 5;
    twice(n);
    printf("%d\n", n);                /* prints 5, not 10 */
    return 0;
}

Pour permettre à une fonction de modifier une variable de l’appelant, ou de renvoyer plus d’un résultat, on passe son adresse : le sujet de la leçon sur les pointeurs, et la raison pour laquelle scanf veut &n.

Portée et durée de vie des variables

  • Les variables locales, déclarées à l’intérieur d’une fonction ou d’un bloc, n’existent que pendant l’exécution de ce bloc et ne sont visibles que là.
  • Les variables globales, déclarées en dehors de toute fonction, existent pendant tout le programme et sont visibles partout. Commodes mais dangereuses : n’importe quelle fonction peut les modifier, et trouver laquelle l’a fait est difficile.
  • Une variable locale static conserve sa valeur entre les appels : utile pour un compteur interne à une fonction.

La pile d’appels

Chaque appel de fonction crée en mémoire un enregistrement d’activation (stack frame) qui contient les paramètres, les variables locales et l’adresse de retour. Les enregistrements s’empilent sur la pile : celui du dessus est la fonction en cours d’exécution ; au return il est retiré et l’exécution reprend dans l’appelant.

C’est pourquoi les variables locales « disparaissent » à la fin de la fonction : leur espace est réutilisé par l’appel suivant. Renvoyer l’adresse d’une variable locale est l’une des erreurs les plus graves en C.

La récursivité

Une fonction récursive s’appelle elle-même sur un problème plus petit. Elle a besoin de deux ingrédients : un cas de base résolu directement et un pas récursif qui réduit le problème vers le cas de base.

unsigned long fact(unsigned int n)
{
    if (n <= 1) return 1;          /* base case */
    return n * fact(n - 1);        /* recursive step */
}
La pile d'appels pendant le calcul récursif de fact(3)
Sur la figure la fonction fact est appelée f. Pendant le calcul de f(3) trois enregistrements d’activation s’empilent sur celui de main. Quand f(1) renvoie 1, les enregistrements sont retirés un par un : f(2) renvoie 2, f(3) renvoie 6.

La récursivité est naturelle pour les problèmes qui contiennent des copies plus petites d’eux-mêmes : structures arborescentes, algorithmes « diviser pour régner » comme le tri fusion et la FFT, exploration d’un labyrinthe.

Les coûts. Chaque appel prend de la place sur la pile. Avec une récursivité trop profonde la pile s’épuise (dépassement de pile, stack overflow) et le programme plante : un risque réel sur les microcontrôleurs, où la pile fait quelques kilo-octets. Certaines récursivités répètent aussi beaucoup de travail : Fibonacci écrit sous la forme fib(n) = fib(n-1) + fib(n-2) recalcule les mêmes valeurs un nombre exponentiel de fois ; fib(40) demande plus de 300 millions d’appels. La version avec une boucle demande 40 pas.

unsigned long fib(unsigned int n)
{
    unsigned long a = 0, b = 1;
    for (unsigned int i = 0; i < n; i++) {
        unsigned long t = a + b;
        a = b;
        b = t;
    }
    return a;
}

Concevoir avec des fonctions

Une bonne fonction fait une seule chose, a un nom qui la décrit, peu de paramètres et pas d’effets de bord cachés. On peut la vérifier seule, avec un petit programme de test qui l’appelle avec des valeurs dont le résultat est connu : l’idée des tests unitaires. La bibliothèque standard du C (<math.h>, <string.h>, <stdlib.h>) est un exemple de petites fonctions réutilisables : avant d’en écrire une, vérifiez si elle n’existe pas déjà.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x