Et moi je te dis que si. Il y aura une optimisation pour transformer la récursion en boucle (ou pas), mais ce code est du C parfaitement valide. Il n'y a pas de discussion possible ici : il est écrit en C, qui autorise la récursion.
Et ce code à clairement un fuite mémoire sans l’implémentation de l’optimisation de la récursion terminale (ce qui est un bug).
Non. Car je le répète, le C n'impose pas l'utilisation d'une pile. La fonction loop ci-dessus ne fait absolument aucune allocation — outre le fait qu'effectivement, il faut trouver un moyen de garder les pointeurs msg successifs en mémoire, mais ce n'est pas un problème du langage, car encore une fois, il ne suppose rien concernant l'organisation de la mémoire physique de la machine (ça se trouve, tout est alloué sur le tas, ou bien le PC a une pile de taille infinie, etc.). De même qu'écrire ceci est valide :
while(1);// nothing
La transformation d’appel récursif vers une boucle est une optimisation dans le cas des langages impératifs (ce n’est pas dans la norme) mais une fonctionnalité dans les langages fonctionnelles (garantie par la norme). En théorie ça pourrait être différent, mais en pratique c’est ce que l’on observe.
Uniquement dans les langages fonctionnels purs, alors. Car j'ai déjà donné l'exemple de Common LISP qui n'a aucune garantie dans la norme à ce sujet. Ensuite, comme tu le dis, il s'agit d'une optimisation pour les langages impératifs, ce qui indique bien que le programme est parfaitement valide lorsqu'il est exécuté sur une machine abstraite (et c'est tout ce qu'on demande à une norme, qui ne peut prévoir tous les progrès architecturaux à venir).
Cette différence de statut (fonctionnalité/optimisation) n’est pas un simple détail ! Elle change la façon dont on programme. En pratique personne ne programme en récursif en dehors des langages fonctionnels (en tout cas c’est minoritaire), ce n’est pas du tout l’esprit.
Oui, évidemment, on utilise beaucoup de constructions itératives dans les langages impératifs. Mais dire qu'en pratique on ne pratique pas la récursion, c'est un peu osé.
L’optimisation de la récursion terminale fait partie de l’esprit de la programmation fonctionnel, mais pas de celui de la programmation impérative.
Transformer un appel récursif terminal en boucle est une obligation pour un langage fonctionnel pur (i.e., qui n'accepte pas les boucles), pour les raisons pratiques que tu as évoquées. Un langage impératif a déjà une façon d'exprimer le résultat final à travers une boucle directement. Dans les deux cas, la transformation d'une récursion terminale vers une boucle est un cas qui n'est pas réservé à un style de programmation : impératif ou fonctionnel, à partir du moment où tu acceptes qu'une fonction peut être récursive, alors la spécification de ton programme dit que toute récursion est légale (je grossis le trait mais j'espère que tu comprends ce que je veux dire). La transformation de RT → boucle est possible dès lors que la forme est respectée, et ceci est indépendant du type de langage. Tu peux tenter de nuancer en disant qu'en C ou C++ ce n'est qu'une optimisation, mais la vérité, c'est qu'il existe énormément d'algorithmes qui sont effectivement exprimés sous forme récursive, et qui, pour des raisons de performance, vont être modifiés jusqu'à atteindre une forme récursive terminale. Ensuite on pourrait bien entendu aller à l'étape suivante « directement » (transformer le tout en boucle), mais comme la plupart des compilateurs savent faire les choses correctement, pourquoi s'emmerder ?
[^] # Re: C'est pourtant évident.
Posté par lasher . En réponse à la dépêche Coder efficacement, bonnes pratiques et erreurs à éviter. Évalué à 2.
Et moi je te dis que si. Il y aura une optimisation pour transformer la récursion en boucle (ou pas), mais ce code est du C parfaitement valide. Il n'y a pas de discussion possible ici : il est écrit en C, qui autorise la récursion.
Non. Car je le répète, le C n'impose pas l'utilisation d'une pile. La fonction
loopci-dessus ne fait absolument aucune allocation — outre le fait qu'effectivement, il faut trouver un moyen de garder les pointeursmsgsuccessifs en mémoire, mais ce n'est pas un problème du langage, car encore une fois, il ne suppose rien concernant l'organisation de la mémoire physique de la machine (ça se trouve, tout est alloué sur le tas, ou bien le PC a une pile de taille infinie, etc.). De même qu'écrire ceci est valide :Uniquement dans les langages fonctionnels purs, alors. Car j'ai déjà donné l'exemple de Common LISP qui n'a aucune garantie dans la norme à ce sujet. Ensuite, comme tu le dis, il s'agit d'une optimisation pour les langages impératifs, ce qui indique bien que le programme est parfaitement valide lorsqu'il est exécuté sur une machine abstraite (et c'est tout ce qu'on demande à une norme, qui ne peut prévoir tous les progrès architecturaux à venir).
Oui, évidemment, on utilise beaucoup de constructions itératives dans les langages impératifs. Mais dire qu'en pratique on ne pratique pas la récursion, c'est un peu osé.
Transformer un appel récursif terminal en boucle est une obligation pour un langage fonctionnel pur (i.e., qui n'accepte pas les boucles), pour les raisons pratiques que tu as évoquées. Un langage impératif a déjà une façon d'exprimer le résultat final à travers une boucle directement. Dans les deux cas, la transformation d'une récursion terminale vers une boucle est un cas qui n'est pas réservé à un style de programmation : impératif ou fonctionnel, à partir du moment où tu acceptes qu'une fonction peut être récursive, alors la spécification de ton programme dit que toute récursion est légale (je grossis le trait mais j'espère que tu comprends ce que je veux dire). La transformation de RT → boucle est possible dès lors que la forme est respectée, et ceci est indépendant du type de langage. Tu peux tenter de nuancer en disant qu'en C ou C++ ce n'est qu'une optimisation, mais la vérité, c'est qu'il existe énormément d'algorithmes qui sont effectivement exprimés sous forme récursive, et qui, pour des raisons de performance, vont être modifiés jusqu'à atteindre une forme récursive terminale. Ensuite on pourrait bien entendu aller à l'étape suivante « directement » (transformer le tout en boucle), mais comme la plupart des compilateurs savent faire les choses correctement, pourquoi s'emmerder ?