Récursivité en C
Salut à tous,
Soit cette procédure écrite en C qui permet de calculer récursivement la somme de n premiers entiers
void somme(int n,int *s)
{
if (n==0)
*s=0;
else
{
somme(n-1,s);
*s=*s+n;
}
}
J'ai pas compris pourquoi l'instruction somme(n-1,s) vient avant *s=*s+n ??
Ben c'est l'appel récursif. Dans le cas présent, elle pourrait venir après ceci dit.
Mais c'est une écriture bizarre avec le passage du pointeur sur la variable... C'est même assez moche.
J'ai testé le programme en l'écrivant après mais il ne tourne pasEnvoyé par pm42
Parce que somme(n) = somme(n-1) + n
C'est moche parce que la fonction devrait retourner la somme et pas void
J'ai rien compris mes amis :/
Tu n'as pas compris mon message #4?
cette fonction fonctionne ()
pour le programme, je ne me prononce pas, vu que tu ne nous donnes pas le main() qui appelle la fonction.
There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.
elle est très bien cette fonction...
même si je l'aurai plutôt écrit comme ça (pour rester dans l'esprit):
bref, on lance avec n = 5Code:void somme(int n, int *s) { if (n) { somme(n-1, s); *s += n; } else *s = 0; }
la fonction empile jusqu'à être à 0 et donc initialise *s à 0
puis dépile et somme...
pour bien voir ce qu'il se passe, on peut ajouter des printf()...:
ce qui donne :Code:#include <stdio.h> void somme(int n, int *s) { printf("debut somme: n = %d\n",n); if (n) { somme(n-1, s); *s += n; } else *s = 0; printf("fin somme: n = %d *s = %d\n", n, *s); } int main() { int sum; somme(5, &sum); printf("fin main: sum = %d\n", sum); }
Code:debut somme: n = 5 debut somme: n = 4 debut somme: n = 3 debut somme: n = 2 debut somme: n = 1 debut somme: n = 0 fin somme: n = 0 *s = 0 fin somme: n = 1 *s = 1 fin somme: n = 2 *s = 3 fin somme: n = 3 *s = 6 fin somme: n = 4 *s = 10 fin somme: n = 5 *s = 15 fin main: sum = 15
Jusqu'ici tout va bien...
variante plus compacte
Code:#include <stdio.h> int somme(int n) { return (n==0)?0:(n+somme(n-1)) } int main() { printf("fin main: sum = %d\n", somme(10)) }
Dernière modification par jacknicklaus ; 24/01/2018 à 12h41.
There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.
oui, mais on perd le charme de l'usage du pointeur...
( qui n'a pas moins d'intérêt que la récursivité )
sinon:
{ return n ? (n + somme(n - 1)) : 0; }
c'est encore plus compact...
Jusqu'ici tout va bien...
Sûrement.
mais je trouve plus naturel d'en faire une fonction plutôt qu'une procédure.
Ce n'est pas seulement plus naturel, c'est comme cela qu'il faut faire pour plein de bonnes raisons : le pointeur n'est pas "safe" en gestion de mémoire, il n'est pas thread-safe, il empêche éventuellement les preuves de programme en introduisant des effets de bords.
La seule raison de faire comme ça est d'utiliser un accumulateur pour permettre l'optimisation de la récursivité terminale mais je ne suis même pas sur que cela fonctionne dans le cas présent.
C'est très moche. Parce que tu introduis une regrettable confusion entre 0 (entier) et FAUX (booléen).
il se trouve que sa fonctionne, mais ce n'est PAS le même objet.
There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.
En C, cette confusion fait malheureusement partie du langage.
Chacun ses esthétismes...
et pas qu'en C.
même en python.
ça peut être tout ou n'importe quoi comme type d'objet.
d'ailleurs maintenant, je n'écris plus de truc du genre:
if truc == True:
mais juste
if truc:
car si truc == 1, c'est forcement différent de True et je ne vais pas transtyper avec un bool(truc) juste pour consommer du temps cpu...
car truc peut être une chaîne, une liste, un tuple, un dico, un set, un int, un float, un None, ... et même un booléen
d'ailleurs en python, l'usage des booléens est plus coûteux en temps que les bon vieux 0 et 1 (enfin, 1 ou autre int non nul)...
comparez un while True: et while 1: (avec un compteur et un break), vous verrez...
Jusqu'ici tout va bien...
Python est typé dynamiquement donc ce type de "confusion" est intrinsèque. C est typé statiquement mais n'a pas le concept de booléen et fait du "typage faible", c'est plus critiquable même si cela se comprend vu l'époque de sa conception.
Conséquence du typage dynamique qui va imposer des vérifications/conversions. Dans un langage avec typage statique, le compilateur peut générer exactement le même code.
Mais on gagne une chance que le compilateur transforme l'appel de fonction récursif en une simple boucle de traitement.
Si l'on prend le code donné dans le sujet, il y a fort à parier que le compilateur ne saura pas beaucoup l'optimiser, et on se retrouvera au moment de l'exécution avec un enchaînement d'appels à la fonction, avec chaque fois l'ajout de l'adresse de retour et des variables n et s sur la pile. Si la valeur initiale de n est trop élevée, on aura une forte consommation de mémoire sur la pile (précisément de (n+1)*(sizeof(int)+2*sizeof(vo id*)) octets), avec un ralentissement du processus dû aux échanges entre les différents niveaux de cache sur les gros système, ou un débordement de la pile avec plantage du programme sur les petits systèmes.
Si l'on prend le code de jacknicklaus, le compilateur a toutes les chances de transformer la fonction récursive :
en une boucle de la forme :Code:int somme(int n) { return n==0 ? 0 : n+somme(n-1); }
D'une manière générale, même si elle est enseignée dans les écoles pour illustrer certaines possibilités théoriques, en pratique la récursivité (qui est par définition « ce qui est susceptible de se répéter à l'infini ») reste une aberration lorsqu'elle n'est pas précisément maîtrisée. On risque en effet d'aboutir rapidement à des situations catastrophiques alors que par ailleurs le code paraît tout-à-fait correct.Code:int somme(int n) { int register a = 0; while (n!=0) { a += n; n--; } return a; }
Mon expérience la plus emblématique en la matière fut un programme réalisé par l'un de mes sous-traitants pour Windows NT4. Sur les gros PC de l'époque, le traitement qu'il avait choisi de coder avec des appels récursifs prenait environ trois quart d'heures à s'exécuter, et faisait un usage intensif du fichier de swap (le bruit du disque dur en fournissait alors un bon indicateur). Après avoir simplement transformé ces appels, il ne prenait plus que quelques secondes !
Plutôt que d'espérer que le compilateur trouve tout seul le moyen d'améliorer la situation, il est grandement préférable d'adopter soi-même des principes de programmation qui évitent de tels cas de figure. Dès qu'un traitement défini comme récurrent apparaît, le réflexe devrait être de chercher les séquences qu'il sera amené à réaliser afin de le coder à l'aide de boucles classiques.
Cela revient à faire de l’optimisation à la main ou de la dérécursivation.
Sauf cas particulier, on gagne peu sur les machines modernes.
Et le code récursif est en général plus court, plus facile à maintenir et à rendre fiable.
Ce n’est pas un hasard si les langages modernes le mette en avant notamment dans le cadre de l’introduction de la programmation fonctionnelle.
Pour de nombreux programmes actuels, la productivité du développement et la fiabilité sont plus importants que l’optimisation.
Celle ci peut toujours être faite ensuite là où c’est vraiment nécessaire. Knuth disait d’ailleurs déjà ça il y a quels décennies.
De plus un exemple sur NT4 n’est pas vraiment pertinent de nos jours.
J'ai cité un vieil exemple sous NT4 parce que ses conséquences étaient flagrantes et spectaculaires (trois quarts d'heure de swap pour une petite erreur de conception, c'est du jamais vu), mais même si dans des circonstances similaires les machines modernes s'en sortent beaucoup mieux, dans le principe le problème est toujours le même.
Aujourd'hui on pourrait avancer d'une part que le plus souvent la recherche des performances est devenue inintéressante et reste moins prioritaire que la réduction des coûts de production, et d'autre part que les outils de développement parviennent en principe à régler tout seuls les problèmes les plus complexes, notamment ceux liés à l'optimisation.
Mais en réalité on ne peut absolument pas généraliser. Il existe de nombreux domaines dans lesquels les objectifs techniques sont exigeants, passent devant les économies sur le temps (voire la qualification) des développeurs et ne sauraient dépendre du comportement non garanti d'outils de tierce partie.
Le fait est qu'en matière de récursivité (qu'on mettait déjà en avant il y a plus de trente ans), les compilateurs C/C++ actuels ne parviennent pas toujours à faire l'optimisation nécessaire, et les recettes de codage pour forcer un résultat satisfaisant peuvent varier d'une plateforme à l'autre. [NB : d'ailleurs, par curiosité, je viens d'essayer le premier code sur deux compilateurs « up-to-date », et sans surprise ils n'ont pas réussi à faire la transformation espérée.]
Cela est d'autant plus préoccupant que les comportements inadéquats (ralentissement, plantage par débordement de pile) risquent parfois de survenir tardivement, une fois chez l'utilisateur, à la faveur d'une situation particulière que ni le développeur ni ses outils n'auront réussi à anticiper.
Or, on ne peut pas se permettre d'attendre d'avoir constaté les dégâts puis d'être parvenu à retrouver l'origine de la faille pour commencer à faire le travail là où il était finalement nécessaire.
D'où mon conseil d'adopter a priori des principes de programmation permettant d'éviter ce type de cas de figure, où la production d'un code apparemment correct et plus simple à l'aide d'outils sophistiqués (du moins le croit-on) porte en réalité atteinte à la fiabilité du système en augmentant les risques de dysfonctionnement.
De mon point de vue, les appels récursifs ne devraient être utilisés que si l'on peut justifier de leur utilité et de leur totale maîtrise.
