Récursivité en C
Répondre à la discussion
Affichage des résultats 1 à 20 sur 20

Récursivité en C



  1. #1
    hamouda1923

    Question 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 ??

    -----

  2. #2
    pm42

    Re : Récursivité en C

    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.

  3. #3
    hamouda1923

    Re : Récursivité en C

    Citation Envoyé par pm42 Voir le message
    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 pas

  4. #4
    Jack
    Modérateur

    Re : Récursivité en C

    Citation Envoyé par hamouda1923 Voir le message

    J'ai pas compris pourquoi l'instruction somme(n-1,s) vient avant *s=*s+n ??
    Parce que somme(n) = somme(n-1) + n

  5. A voir en vidéo sur Futura
  6. #5
    Jack
    Modérateur

    Re : Récursivité en C

    Citation Envoyé par pm42 Voir le message
    C'est même assez moche.
    C'est moche parce que la fonction devrait retourner la somme et pas void

  7. #6
    hamouda1923

    Re : Récursivité en C

    J'ai rien compris mes amis :/

  8. #7
    Jack
    Modérateur

    Re : Récursivité en C

    Tu n'as pas compris mon message #4?

  9. #8
    jacknicklaus

    Re : Récursivité en C

    Citation Envoyé par hamouda1923 Voir le message
    J'ai testé le programme en l'écrivant après mais il ne tourne pas
    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.

  10. #9
    polo974

    Re : Récursivité en C

    elle est très bien cette fonction...
    même si je l'aurai plutôt écrit comme ça (pour rester dans l'esprit):
    Code:
    void somme(int n, int *s)
    {
        if (n)
        {
            somme(n-1, s);
            *s += n;
        }
        else
            *s = 0;
    }
    bref, on lance avec n = 5
    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()...:

    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);
    }
    ce qui donne :
    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...

  11. #10
    jacknicklaus

    Re : Récursivité en C

    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.

  12. #11
    polo974

    Re : Récursivité en C

    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...

  13. #12
    Jack
    Modérateur

    Re : Récursivité en C

    Citation Envoyé par polo974 Voir le message
    oui, mais on perd le charme de l'usage du pointeur...
    Sûrement.
    mais je trouve plus naturel d'en faire une fonction plutôt qu'une procédure.

  14. #13
    pm42

    Re : Récursivité en C

    Citation Envoyé par Jack Voir le message
    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.

  15. #14
    jacknicklaus

    Re : Récursivité en C

    Citation Envoyé par polo974 Voir le message
    { return n ? (n + somme(n - 1)) : 0; }
    .
    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.

  16. #15
    pm42

    Re : Récursivité en C

    Citation Envoyé par jacknicklaus Voir le message
    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.
    En C, cette confusion fait malheureusement partie du langage.

  17. #16
    polo974

    Re : Récursivité en C

    Citation Envoyé par jacknicklaus Voir le message
    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.
    Chacun ses esthétismes...

    Citation Envoyé par pm42 Voir le message
    En C, cette confusion fait malheureusement partie du langage.
    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...

  18. #17
    pm42

    Re : Récursivité en C

    Citation Envoyé par polo974 Voir le message
    même en python.
    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.

    Citation Envoyé par polo974 Voir le message
    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...
    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.

  19. #18
    PA5CAL

    Re : Récursivité en C

    Citation Envoyé par polo974 Voir le message
    oui, mais on perd le charme de l'usage du pointeur...
    ( qui n'a pas moins d'intérêt que la récursivité )
    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 :
    Code:
    int somme(int n)
    {
      return n==0 ? 0 : n+somme(n-1);
    }
    en une boucle de la forme :
    Code:
    int somme(int n)
    {
      int register a = 0;
      while (n!=0) {
        a += n;
        n--;
      }
      return a;
    }
    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.

    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.
    Dernière modification par PA5CAL ; 30/01/2018 à 12h18.

  20. #19
    pm42

    Re : Récursivité en C

    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.

  21. #20
    PA5CAL

    Re : Récursivité en C

    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.

Discussions similaires

  1. Ecrire les méthodes en récursivité
    Par Christina1414 dans le forum Programmation et langages, Algorithmique
    Réponses: 20
    Dernier message: 24/11/2015, 20h00
  2. Récursivité et SQL
    Par haast dans le forum Programmation et langages, Algorithmique
    Réponses: 5
    Dernier message: 13/11/2014, 21h24
  3. la récursivité
    Par invitee2f3230c dans le forum Logiciel - Software - Open Source
    Réponses: 14
    Dernier message: 06/04/2010, 23h16
  4. récursivité, itération
    Par invite1acecc80 dans le forum Logiciel - Software - Open Source
    Réponses: 6
    Dernier message: 03/02/2010, 11h28
  5. Intégrale et recursivité
    Par Olorin dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 17/01/2005, 12h22