C : coups de cœur et coups de gueule

Un article de Kirilenko    5 Commentaires

Une récursion pour les gouverner tous

Voilà quelques temps que je n’avais plus utilisé ce média ; j’avais posté un article similaire sur une plateforme perdue, mais, n’ayant pas reçu réellement de retour, je me suis dit qu’il serait intéressant de centraliser tous mes petits articles ici, de manière à renvoyer uniformément les visiteurs sur cette page. Au départ, il s’agissait ici de parler uniquement de programmation système ; le sort en a décidé autrement.

En attendant, vous allez devoir me pardonner pour cette digression, qui ne devrait pas vraiment avoir de répercussion sur les visites, ceci dit. Voilà une nouvelle catégorie, « Divers », qui devrait accueillir nombre de mes réflexions inutiles (sur les forums, il est difficile de se lâcher sans se faire taper sur les doigts).

Qu’on se mette d’accord, aujourd’hui, c’est d’un véritable phénomène qu’on va parler. Une habitude étrange que quelques débutants ont prise : effectuer une récursion sur la fonction main. Ce sera notre prétexte pour explorer tout le vaste sujet de la récursivité en C. Je ne sais pas qui le leur a inculqué (ou plutôt, qui n’a pas fait son boulot en le leur empêchant) ; toujours est-il que cela fait frémir la plupart des programmeurs « habitués » sur les forums. Si ce n’est pas votre cas, c’est inquiétant. Du moins, on va essayer de voir si c’est le cas. Et surtout, pourquoi.

Une récursion pour les trouver

Vous êtes ici, sur un billet qui parle du C, et on vous parle d’algorithmique ? Voilà qui semble, à première vue, plutôt contradictoire. Après tout, les gens qui font du C sont plutôt branchés sur le matériel. C’est ça, le (faux) bas niveau. Seulement, la récursivité, c’est, avant toute chose, une manière particulière de définir un algorithme donné, en le définissant par rapport à une entrée plus simple du problème. En programmation, on parlera de récursivité lorsqu’une fonction s’appelle elle-même. Parfois, il y a même des cas de récursivité croisée, ou deux fonctions s’appellent mutuellement. Un exemple plutôt connu est la suite d’Hofstadter.

Prenons maintenant l’exemple (sérieux) d’un algorithme calculant la factorielle d’un nombre entier naturel. Vous pouvez la définir de deux manières différentes :

1) Itérativement : n! = 1 * 2 * … * n.

2) Récursivement : n! = 1 si n = 0 et n * (n – 1)! si n > 0.

Dès ces cas d’école, les puristes commencent à remettre en cause l’efficacité de la solution récursive. En effet, par nature, le C est assez proche de la machine. Chaque appel de fonction nécessite, en théorie, la création d’un cadre de pile (en pratique, certaines de ces fonctions peuvent être inlinées par le compilateur, c’est-à-dire en ajoutant le code directement dans la fonction appelante).

Ce n’est pas une opération particulièrement légère, et, dès qu’on se met à penser à la micro-optimisation, il vaut mieux éviter. En dehors de la performance, cela pose un autre problème : celui de la mémoire. Il faut bien voir que toutes les variables automatiques, les registres de base et de retour notamment, doivent être stockés sur la pile, et ce pour chaque récursion en cours.

En conséquence, le compilateur essaye de transformer des cas récursifs simples en boucles (qui, au final, auront l’air d’un branchement inconditionnel, équivalent à un vulgaire goto). Il est bien connu que tout appel récursif peut être converti en itératif, par l’intermédiaire de piles (en recodant la pile d’appels en fait), mais, naturellement, ça n’aurait pas de sens pour le compilateur de faire ce genre d’optimisations. Cependant, supposez que vous ayez choisi de coder la factorielle de cette manière :

Parce que r indique les résultats de la récursivité au fur et à mesure, on dit qu’il sert d’accumulateur. En outre, on remarque ici que l’appel récursif peut être facilement évité : il suffit de changer la valeur de r et de n à chaque fin de branchement. Mettons-nous à la place du compilateur optimisant (c’est le cas de la plupart des compilateurs « grands publics » comme gcc, clang ou icc). Voilà comment il pourrait réécrire le code.

Je ne suis pas certain que beaucoup d’entre vous aimerait maintenir ce genre de code, mais, pour la bêtise absolue d’un ordinateur, ce n’est pas dérageant. Au contraire, comme sa fainéantise est légendaire, il va se réjouir de pas avoir à créer un nouveau cadre de pile à chaque fois qu’on décrémente n. On parle dans ce cas de récursivité terminale, et ce n’est pas le cas de la fonction factorial_2 ci-dessus. Bref, tout ça pour dire quoi ? Que la récursivité, c’est intrinsèquement de l’algorithmique. Ça fait plaisir aux férus de la programmation fonctionnelle, mais ça ne devrait pas atteindre nos points d’entrée… Enfin, en théorie.

Une récursion pour les amener tous

Venons-en au fait. Enfin, presque. Oui, parce que je voulais vous présenter mon nouveau jeu en console puissant. Du coup, j’ai fait une jolie interface avec une fonction juste pour le menu. Voilà à quoi ressemble notre bête :

Sauf que, si je laisse ça comme ça, il y a danger. Danger que la pile explose, en réalité. Elle a une taille limitée, et un utilisateur malicieux pourrait même exploiter ces débordements pour écrire par-dessus certaines données (mais ça rentre dans des techniques d’exploitation plutôt sordides). Dans une certaine mesure, même dans les langages fonctionnels (oui, oui), on évite généralement les systèmes récursifs pour lire des données structurées comme les tableaux. Pour les listes ou les arbres, c’est différent, mais, même en C, la question se pose.

En fait, toutes ces histoires de puristes restent extrêmement subjectives. Notre fonction menu ci-dessus croît selon un majorant en O(n). En revanche, il existe certaines fonctions qui ont une complexité bien moindre. C’est par exemple le cas de la recherche dichotomique, qui permet de rechercher une valeur dans un tableau trié en complexité logarithmique (par le biais du paradigme « diviser pour régner »). Ainsi, cela ne posera pas trop de problème à un programmeur d’écrire :

Pourtant, la solution itérative est tout aussi limpide. Du coup, la récursivité se justifie encore plus facilement quand on est obligé de sortir un modèle à base de pile pour la conversion. C’est par exemple le cas des parsers d’expression, quand on doit explorer des caractères sémantiques par définition récursifs (comme les parenthèses dans un parser d’expressions mathématiques).

… et dans les ténèbres les lier

Il est temps de discuter ce qui devait être notre objet initial, mais, qui, finalement, est passé au travers de ma langue bavarde. Oui, parce qu’il existe des pauvres fous (fuyez !) qui, non contents de faire de la récursion sur des menus, le font dans la fonction main ! On voit quelques fois un exemple de récursivité croisée, quand les débutants veulent revenir au début du programme, alors qu’ils sont perdus dans des structures conditionnelle imbriquées.

Le mieux, dans ce genre de code, c’est de passer à la boucle (en ré-arrangeant le code dans un premier temps, évidement…) ; cela pour deux raisons majoritairement :

Pour finir, j’aimerais simplement vous montrer un petit contre-exemple, que quelqu’un proposait sur Usenet. Le principe est d’utiliser la récursivité sur la fonction main pour simplifier le traitement des arguments en ligne de commande. Personnellement, je n’ai jamais eu affaire à ce genre de contraintes, mais on ne sait jamais sur quoi on peut tomber (sans getopt, certains sont perdus !).

Voilà qui clôt magistralement mal notre modeste billet. J’espère ne pas trop vous avoir ennuyé, et n’oubliez pas de rediriger le prochain inconscient par ici… non sans l’avoir châtié sévèrement, évidemment !

PS : Comme habituellement, ça fait toujours du plaisir de voir ses posts commentés… Même si vous n’avez rien à dire, ça donne l’impression qu’on ne parle pas dans le vide. Sauf si vous ne voulez plus jamais me voir appuyer sur une touche du clavier, auquel cas je vous laisse déverser votre haine dans le silence. Le train de vos injures roule sur les rails de mon indifférence, disait un proverbe populaire.