IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Shell et commandes GNU Discussion :

Récursivité, ou pas ?


Sujet :

Shell et commandes GNU

  1. #1
    Modérateur
    Avatar de N_BaH
    Profil pro
    Inscrit en
    Février 2008
    Messages
    7 539
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Février 2008
    Messages : 7 539
    Points : 19 361
    Points
    19 361
    Par défaut Récursivité, ou pas ?
    Bonjour à tous,

    ici, je lis
    Citation Envoyé par Sve@r
    [...]la factorielle sans boucle ni récursivité
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    #!/bin/bash
     
    test -z "$arg" && arg=$1 && res=1
    test $arg -eq 0 && echo $res && exit 0
    res=$(($res * $arg))
    arg=$(($arg - 1))
    source $0
    moi, je vois de la récursivité dans un script qui se source lui-même, mais s'appellerait-il (sans se sourcer), jusqu'à une condition donnée, que j'en verrais encore...
    Citation Envoyé par Sve@r
    Ressembler n'est pas jouer. Comme Canada Dry. Ca a la couleur de l'alcool, son nom sonne comme un nom d'alcool mais ce n'en est pas. Donc ça a la couleur de la récursivité, son nom sonne comme un nom de récursivité... mais ce n'en est pas

    Ceci dit, effectivement je pense qu'un débat à ce propos intéresserait pas mal de monde. Peut-être dans une section plus générale du shell...
    j'ouvre donc le débat.
    .
    N'oubliez pas de consulter les cours shell, la FAQ, et les pages man.

  2. #2
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    Par défaut
    Bonjour

    Ce qui serait plus constructif serait que ceux qui pensent que ce code n'est pas récursif nous explique pourquoi, selon eux.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  3. #3
    Membre averti
    Homme Profil pro
    [SciComp]
    Inscrit en
    Août 2013
    Messages
    134
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : [SciComp]

    Informations forums :
    Inscription : Août 2013
    Messages : 134
    Points : 323
    Points
    323
    Par défaut
    Pour moi aussi, c'est récursif.

    Pour l'opinion contraire, les amateurs comme moi (je n'ai utilisé source que pour sourcer des variables...) auraient pu penser à "source" comme un "include" agissant non au runtime mais en style préprocesseur, mais ça n'est pas le cas selon l'aide de bash.

    Cordialement,
    xflr6

  4. #4
    Expert éminent Avatar de BufferBob
    Profil pro
    responsable R&D vidage de truites
    Inscrit en
    Novembre 2010
    Messages
    3 035
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : responsable R&D vidage de truites

    Informations forums :
    Inscription : Novembre 2010
    Messages : 3 035
    Points : 8 400
    Points
    8 400
    Par défaut
    http://fr.wikipedia.org/wiki/Récursivité :
    La récursivité est une démarche qui fait référence à l'objet de la démarche. Ainsi, les cas suivants constituent des cas concrets de récursivité :
    (...)
    • Écrire un algorithme qui s'invoque lui-même.
    (...)
    En informatique et en logique, une fonction ou plus généralement un algorithme qui contient un appel à elle-même est dite récursive.
    ça revient à considérer ce que fait le code plutôt que l'interface qu'il utilise pour le faire, ça a du sens non ?

  5. #5
    Expert éminent sénior Avatar de disedorgue
    Homme Profil pro
    Ingénieur intégration
    Inscrit en
    Décembre 2012
    Messages
    4 266
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur intégration
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Décembre 2012
    Messages : 4 266
    Points : 12 681
    Points
    12 681
    Par défaut
    Bonjour,
    En principe, dans la récursivité, il y a une notion de pile. Ici je vois plus une notion de Méta-programmation (une forme de duplication de données qui devient du code).

    PS: un simple code de factoriel(6): echo $(($(seq -s '*' 1 6)))
    Cordialement.

  6. #6
    Membre averti
    Homme Profil pro
    [SciComp]
    Inscrit en
    Août 2013
    Messages
    134
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : [SciComp]

    Informations forums :
    Inscription : Août 2013
    Messages : 134
    Points : 323
    Points
    323
    Par défaut
    Bonjour,

    Citation Envoyé par disedorgue Voir le message
    dans la récursivité, il y a une notion de pile.
    "pile" me semble plus connoté "structure de données" alors que récursif est vraiment connoté "action dont la réal appelle à renouveler action".
    Certes, on peut sans doute utiliser une technique de récursion pour aller chercher dans une pile, mais c'est à mon sens plus général que ça.


    Citation Envoyé par disedorgue Voir le message
    Ici je vois plus une notion de Méta-programmation (une forme de duplication de données qui devient du code).
    C'était le sens de mon commentaire qques posts plus haut:
    [On pourrait] penser à "source" comme un "include" agissant non au runtime mais en style préprocesseur, mais ça n'est pas le cas selon l'aide de bash.
    En effet,
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    $ help source
    source: source nom_fichier [arguments]
        Execute des commandes depuis un fichier dans le shell actuel.
     
        Lit et exécute des commandes depuis NOMFICHIER dans le shell actuel.  Les
        éléments dans $PATH sont utilisés pour trouver le répertoire contenant NOMFICHIER.
        Si des ARGUMENTS sont fournis, ils deviennent les paramètres de position
        lorsque NOMFICHIER est exécuté.
     
        Code de sortie :
        Renvoie le code de la dernière commande exécutée dans NOMFICHIER, ou le code
        d'échec si NOMFICHIER ne peut pas être lu.
    qui me donne vraiment l'impression que c'est au runtime que c'est effectué.

    De toute manière, on ne pourrait pas sortir de la duplication sans exécuter la commande test $arg -eq 0 && echo $res && exit 0.
    Donc que ce soit du point de vue "codeur" ou du point de vue "interpréteur", c'est selon moi récursif.

    Cordialement,
    xflr6

  7. #7
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 631
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 631
    Points : 30 865
    Points
    30 865
    Billets dans le blog
    1
    Par défaut
    Bonjour

    J'aime bien la remarque sur la notion de pile car elle est importante. En effet, il est arrivé parfois que certains codeurs simulent la récursivité en empilant et dépilant eux-mêmes les informations nécessaires au calcul sans passer par le mécanisme récursif qui va lui, empiler et dépiler tout l'environnement de travail (c'est plutôt vu dans des langages comme le C ou le Pascal). Ca arrive surtout quand la vitesse est importante et que le mécanisme récursif est trop coûteux en temps.
    Dans ce cas là, le code n'est pas considéré comme du code récursif.

    Ici c'est pareil. Il n'y a pas d'empilement. Le shell déroule et exécute juste un code qui se génère au fur et à mesure. Par exemple, pour la factorielle de 3, ce code sera
    Code bash : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    #!/bin/bash
     
    test -z "$arg" && arg=3 && res=1                        # Ici arg vaut 3 et res vaut 1
    test $arg -eq 0 && echo $res && exit 0                 # Le test est faux
    res=$(($res * $arg))                                          # Ici res vaut 3
    arg=$(($arg - 1))                                               # Ici arg vaut 2
     
    #!/bin/bash                   # Comme il n'est pas sur la première ligne ça devient un simple commentaire
     
    test -z "$arg" && arg=3 && res=1                        # Ici arg vaut 2 et res vaut 3
    test $arg -eq 0 && echo $res && exit 0                 # Le test est faux
    res=$(($res * $arg))                                          # Ici res vaut 6
    arg=$(($arg - 1))                                               # Ici arg vaut 1
     
    #!/bin/bash                   # Comme il n'est pas sur la première ligne ça devient un simple commentaire
     
    test -z "$arg" && arg=3 && res=1                        # Ici arg vaut 1 et res vaut 6
    test $arg -eq 0 && echo $res && exit 0                 # Le test est faux
    res=$(($res * $arg))                                          # Ici res vaut 6
    arg=$(($arg - 1))                                               # Ici arg vaut 0
     
    #!/bin/bash                   # Comme il n'est pas sur la première ligne ça devient un simple commentaire
     
    test -z "$arg" && arg=3 && res=1                        # Ici arg vaut 0 et res vaut 6
    test $arg -eq 0 && echo $res && exit 0                 # Le test est vrai donc affichage 6 et sortie du shell

    Ce code est-il un code récursif ??? Le shell n'a fait que dérouler une suite d'instructions et de calculs sans mettre en jeu le lourd mécanisme d'empilement/dépilement nécessaire à la récursivité. Bien entendu ça a l'esprit de la récursivité, mais ce n'en est pas.

    PS: j'ai bien aimé le code de disedorgue
    D'ailleurs son code comme le mien font tous deux appels à des possibilités offertes par les outils de notre environnement. Moi j'utilise une possibilité offerte par le runtime (certains l'ont appelé "préprocesseur") et lui un outil extérieur qui affiche une séquence.
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  8. #8
    Expert éminent Avatar de BufferBob
    Profil pro
    responsable R&D vidage de truites
    Inscrit en
    Novembre 2010
    Messages
    3 035
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : responsable R&D vidage de truites

    Informations forums :
    Inscription : Novembre 2010
    Messages : 3 035
    Points : 8 400
    Points
    8 400
    Par défaut
    salut,

    Citation Envoyé par Sve@r Voir le message
    Ce code est-il un code récursif ??? Le shell n'a fait que dérouler une suite d'instructions et de calculs sans mettre en jeu le lourd mécanisme d'empilement/dépilement nécessaire à la récursivité.
    ben on pourrait penser que si justement, on prend un code en 3 partie; 1-début, 2-sourcing, 3-suiteducode, l'interpréteur évalue la 1ere partie, puis... la 2e ? donc il source le même script, évalue à nouveau la 1ère partie etc. et pour revenir à la partie 3-suiteducode il a forcément du stacker quelque chose un moment donné à mon sens, elle est là la récursivité

    edit: c'est même assez limpide pour ma part, ça l'aurait été beaucoup moins avec un truc genre exec $0 par exemple

  9. #9
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    Par défaut
    • Bien vu! J'allais dire pareil.
    • Que veut dire GNU ?
      "GNU" = "GNU not Unix"

      Que veut dire Wine ?
      "Wine" = "Wine Is Not an Emulator"

      Voilà des acronymes récursifs. Il n'y a aucune pile.
    • Seuls ceux qui ont eu le plaisir de faire exploser une pile par "stack overflow" comprennent que la récursivité, ça n'est joli que pour les mathématiciens. Sinon, c'est une horreur. Mais de nos jours, les piles sont très grosses.
    • "action dont la réal appelle à renouveler action"
      Hum. Là tu abordes la nuance entre itératif et récursif. Ce qui fait qu'on parle de "récursion" est l'appel à soi-même. Le fait que les instructions soient réitérées n'est qu'un dommage collatéral.
    • Toute boucle ne pourrait-elle pas être considérée comme récursive car se rebranchant sur son début continuellement ?
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  10. #10
    Membre averti
    Homme Profil pro
    [SciComp]
    Inscrit en
    Août 2013
    Messages
    134
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : [SciComp]

    Informations forums :
    Inscription : Août 2013
    Messages : 134
    Points : 323
    Points
    323
    Par défaut
    Pour la différence entre récursif et itératif, il y a dans mon ressenti une notion de scope.
    Pour moi, la décision de renouveler l'action en itératif est prise en dehors de l'algo à l'intérieur de la boucle, alors qu'en récursif, elle est dedans. Non ?

    Cordialement,
    xflr6.

  11. #11
    Expert éminent Avatar de BufferBob
    Profil pro
    responsable R&D vidage de truites
    Inscrit en
    Novembre 2010
    Messages
    3 035
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : responsable R&D vidage de truites

    Informations forums :
    Inscription : Novembre 2010
    Messages : 3 035
    Points : 8 400
    Points
    8 400
    Par défaut
    du coup que penser d'un truc comme ça (hormis que c'est crado ) :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    #!/bin/bash
    [[ $2 = $1 ]] && {
       s=${3:1}
       echo -ne "$1! = $s\n$1! = $((s))\n"
       exit 0
    } || {
       i=$(($2+1))
       exec $0 $1 $i "${3}*${i}"
    }
    et l'invocation :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    $ ./factorielle 6
    6! = 1*2*3*4*5*6
    6! = 720
    récursif ou pas ?

  12. #12
    Expert éminent sénior Avatar de disedorgue
    Homme Profil pro
    Ingénieur intégration
    Inscrit en
    Décembre 2012
    Messages
    4 266
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur intégration
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Décembre 2012
    Messages : 4 266
    Points : 12 681
    Points
    12 681
    Par défaut
    Citation Envoyé par xflr6 Voir le message
    Pour la différence entre récursif et itératif, il y a dans mon ressenti une notion de scope.
    Pour moi, la décision de renouveler l'action en itératif est prise en dehors de l'algo à l'intérieur de la boucle, alors qu'en récursif, elle est dedans. Non ?
    Je suis d'accord sur ce point de vu, on pourrait même rajouter que dans l'itératif, la décision d'arrêt est visible ce qui permet parfois aux compilateur de supprimer une boucle itérative en calculant directement son résultat.
    Dans le récursif, il y a aussi une notion de réentrance, et dans le cas du sourcing, peut-on dire qu'il y a réentrance ?

    En tout cas, le récursif n'est pas à proscrire quand on connait la limite de profondeur.
    Lors de mes études en fac, j'ai eu à programmer les règles du jeux de dame (règle française), j'ai présenté 2 versions:
    Une itérative qui faisait environ 200 lignes mais que tout le monde pouvait comprendre en lisant le code.
    Puis une version récursive sur 3 fonctions => 30 lignes de code, mais là, même le prof était perplexe sur le fonctionnement

    PS: une méthode builtin pour CERTAINES version bash (4.1.4): echo $(($(echo {1..6}'*')1))
    Cordialement.

  13. #13
    Expert éminent sénior Avatar de Flodelarab
    Homme Profil pro
    Inscrit en
    Septembre 2005
    Messages
    5 238
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Charente (Poitou Charente)

    Informations forums :
    Inscription : Septembre 2005
    Messages : 5 238
    Points : 13 443
    Points
    13 443
    Par défaut
    Très important de toujours multiplier par 1

    Mais dans cette dernière version le 6 n'est pas variable.

    Alors que "echo $(($(seq -s '*' 1 6)))" peut être changé par "echo $(($(seq -s '*' 1 $n)))". Auquel cas le 1 est important.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  14. #14
    Expert éminent sénior Avatar de disedorgue
    Homme Profil pro
    Ingénieur intégration
    Inscrit en
    Décembre 2012
    Messages
    4 266
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur intégration
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Décembre 2012
    Messages : 4 266
    Points : 12 681
    Points
    12 681
    Par défaut
    Ok, une version builtin bash variabilisée:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    X=6 && printf -v YY "%0${X}d\n" 0 && echo $((${YY//0/X--*}1))
    Là pour le coups, peut-on considérer qu'elle est récursive ?
    Cordialement.

  15. #15
    Membre averti
    Homme Profil pro
    [SciComp]
    Inscrit en
    Août 2013
    Messages
    134
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : [SciComp]

    Informations forums :
    Inscription : Août 2013
    Messages : 134
    Points : 323
    Points
    323
    Par défaut
    Non, mais c'est joli.
    - Je ne connaissais pas le printf dans une variable [mon man non plus d'ailleurs ?],
    - Je n'avais jamais osé les opérateurs increment/decrement en bash.
    Ca va m'être utile, merci.

    xflr6

  16. #16
    Expert éminent sénior
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 631
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 631
    Points : 30 865
    Points
    30 865
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par Flodelarab Voir le message
    Que veut dire GNU ?
    "GNU" = "GNU not Unix"

    Que veut dire Wine ?
    "Wine" = "Wine Is Not an Emulator"

    Voilà des acronymes récursifs. Il n'y a aucune pile.
    Définition donnée pour ces acronymes de façon humoristique. Conceptuellement ce ne sont pas des acronymes vraiment récursifs sinon chacun devrait être redécrit à chaque fois qu'on l'écrit et ça partirait à l'infini.
    Ce n'est pas parce que les créateurs de ces acronymes ont employé le terme "récursif" (ce sont tous des acronymes informatiques donc ils ont voulu donner leur donner un adjectif à connotation informatique) que c'est du vrai récursif et qu'on peut alors les utiliser comme base de référence pour définir ce qui est récursif et ce qui ne l'est pas. http://fr.wikipedia.org/wiki/R%C3%A9...A9#cite_note-3.

    Citation Envoyé par Flodelarab Voir le message
    Toute boucle ne pourrait-elle pas être considérée comme récursive car se rebranchant sur son début continuellement ?
    Je crois qu'on inverse le problème. Un peu comme Pythagore quand il disait que le nombre 10 était un nombre parfait et que même les dieux le savaient car ils nous avaient donnés dix doigts. Les premiers langages ne connaissaient pas la récursivité. Celui qui voulait explorer un arbre en profondeur devait se débrouiller pour empiler/dépiler lui-même ses éléments de recherche. Je me souviens de mon premier code en Basic où je voulais afficher toutes les lettres de "aaaaaaaaa" jusqu'à "zzzzzzzzz" pour reproduire l'intrigue de la nouvelle d'Arthur C. Clarke. Ca avait l'air trivial pourtant j'en ai bavé. Ensuite, quand je l'ai réécrit en C ça a été effectivement beaucoup plus trivial...

    Ensuite les concepteurs de langages ont automatisé cet empilement/dépilement ce qui a permis effectivement de créer les structures de boucles. En effet, devoir se rebrancher sur le début correspondant à la fin de boucle implique forcément un empilement de chaque début de boucle et un dépilement en fin de boucle pour pouvoir revenir à ce début. Et ça je l'ai compris le jour où j'ai voulu écrire mon compilateur Brainfuck et où j'ai dû empiler chaque position correspondant à "[" (début de boucle) pour pouvoir y revenir (goto) chaque fois que je tombais sur un "]" (fin de boucle).
    Ca a permis aussi de créer la récursivité (permettre à une fonction de s'appeler elle-même). Mais empiler/dépiler n'est pas du récursif. Certes la récursivité exige de l'empilement (pour pouvoir revenir en fin d'action au point où l'action commence) mais on peut très bien écrire soi-même cet empilement pour arriver au résultat. Et dans ce cas, ce n'est plus du récursif. C'est plutôt un retour à "avant" la récursivité. D'ailleurs même moi je me trompe quand je dis qu'on "simule" la récursivité. C'est plutôt la récursivité qui "simule" (ou plutôt "automatise") un algorithme fait à partir d'empilements/dépilements de ses éléments nécessaires...

    Bien entendu que mon code est récursif. D'ailleurs on ne peut pas calculer la factorielle sans passer soit par du récursif, soit par de l'itératif. Mais ma récursivité était cachée derrière un outil qui, BufferBob l'a bien fait remarquer, est forcément récursif. Mon trait était plutôt un trait d'humour pour MR-SMOOT (débutant) que je comptais plonger dans une amusante perplexité.
    Ce trait est d'ailleurs repris avec autant d'humour par disedorgue qui utilise, lui, de l'itératif caché derrière des outils de répétition...

    PS: un code moins crado pour BufferBob qui a suggéré la possibilité exec...
    Code bash : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    #!/bin/bash
     
    res=${2:-1}
     
    test $1 -gt 1 && exec $0 $(($1 - 1)) $(($1 * $res))
    echo $res
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  17. #17
    Expert éminent sénior Avatar de disedorgue
    Homme Profil pro
    Ingénieur intégration
    Inscrit en
    Décembre 2012
    Messages
    4 266
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur intégration
    Secteur : High Tech - Opérateur de télécommunications

    Informations forums :
    Inscription : Décembre 2012
    Messages : 4 266
    Points : 12 681
    Points
    12 681
    Par défaut
    Citation Envoyé par xflr6 Voir le message
    - Je ne connaissais pas le printf dans une variable [mon man non plus d'ailleurs ?],
    Ici, j'utilise la builtin bash, donc tu peux le voir en utilisant le help de bash qui est très utile:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    $ help printf
    printf: printf [-v var] format [arguments]
        Formats and prints ARGUMENTS under control of the FORMAT.
     
        Options:
          -v var	assign the output to shell variable VAR rather than
        		display it on the standard output
    ...
    ...
    Citation Envoyé par Flodelarab Voir le message
    • Toute boucle ne pourrait-elle pas être considérée comme récursive car se rebranchant sur son début continuellement ?
    Sve@r à déjà très bien débattu ce point, mais rappelons aussi que la boucle fait partie intégrante des instructions processeur via ces débranchements conditionnels.
    Cordialement.

  18. #18
    Membre averti
    Homme Profil pro
    [SciComp]
    Inscrit en
    Août 2013
    Messages
    134
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Essonne (Île de France)

    Informations professionnelles :
    Activité : [SciComp]

    Informations forums :
    Inscription : Août 2013
    Messages : 134
    Points : 323
    Points
    323
    Par défaut
    Citation Envoyé par Sve@r Voir le message
    le jour où j'ai voulu écrire mon compilateur Brainfuck
    Je vois un soupçon de récursivité là-dedans

  19. #19
    Expert confirmé
    Homme Profil pro
    Développeur informatique en retraite
    Inscrit en
    Avril 2008
    Messages
    2 101
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côtes d'Armor (Bretagne)

    Informations professionnelles :
    Activité : Développeur informatique en retraite

    Informations forums :
    Inscription : Avril 2008
    Messages : 2 101
    Points : 5 849
    Points
    5 849
    Par défaut
    Citation Envoyé par Flodelarab Voir le message
    Seuls ceux qui ont eu le plaisir de faire exploser une pile par "stack overflow" comprennent que la récursivité, ça n'est joli que pour les mathématiciens. Sinon, c'est une horreur.
    C'est du troll ou quoi?

    Pour ma part, il me semble intéressant de distinguer les différents "types" de récursivité en fonction du nombre de réentrances (appels de "foo" dans l'implémentation de "foo")

    • 1
      Lorsqu'il n'y en a qu'une (comme pour la factorielle), l'algo peut la plupart du temps être transformé en récusivité terminale voire en simple itération (donc pas besoin de pile).

    • 2 ou plus (mais fixe)
      Lorsque le nombre d'appels est fixe, mais supérieur à 1, c'est déjà plus délicat.
      Le cas simple est "fibonacci" qui, de récursif (à 2 appels réentrants):
      Code : Sélectionner tout - Visualiser dans une fenêtre à part
      1
      2
      3
      4
      5
      define fibonacci (N)
      if N == 0 or N == 1
      then return N
      else return fibonacci (N - 1) + fibonacci (N - 2)
      fi
      peut facilement (mais astucieusement) être converti en itératif:
      Code : Sélectionner tout - Visualiser dans une fenêtre à part
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      define fibonacci (N)
      fibN-2 := 0
      fibN-1 := 1
      fibN := fibN-2
      for I from 1 to N do
        fibN := fibN-1 + fibN-2
        fibN-2 := fibN-1
        fibN-1 := fibN
      done
      return fibN
      Pour l'exploration d'un arbre binaire, c'est déjà moins simple et le récursif s'impose généralement:
      Code : Sélectionner tout - Visualiser dans une fenêtre à part
      1
      2
      3
      4
      define GRD (tree)
      if left(tree) is_a_tree then GRD(left(tree)) fi
      racine(tree)
      if right(tree) is_a_tree then GRD(right(tree)) fi
    • X (variable)
      Le cas le plus courant est celui de l'exploration d'un arbre N-aire
      Par exemple, dans beaucoup de jeux, dans chaque position, j'ai un certain nombre de coups à ma disposition. Pour chacun de ces coups, j'obtiens une nouvelle position, et je plonge jusqu'à... soit trouver ce que je cherche (solution, gain, perte, etc.) soit j'arrête à une profondeur donnée ou après un temps donné parce que sinon ça va coûter trop cher!
      Dans ces cas-là, l'écriture récursive est beaucoup plus simple à écrire, lire et maintenir, et on laisse le compilateur ou l'interpréteur gérer le boulot (trivial) de la récursivité (empilement, gestion du contexte et des valeurs de retour).
      Code : Sélectionner tout - Visualiser dans une fenêtre à part
      1
      2
      3
      4
      define explore (tree)
      for subtree in subtrees(tree)
      do explore subtree
      done
      Et puis il y a les cas "tordus"...
      Challenge: Quelqu'un a-t-il une implémentation non récursive de la fonction d'Ackermann?


    Mais de nos jours, les piles sont très grosses.
    Comme ça, on peut repousser les limites pour la profondeur d'exploration!

  20. #20
    Expert éminent Avatar de BufferBob
    Profil pro
    responsable R&D vidage de truites
    Inscrit en
    Novembre 2010
    Messages
    3 035
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations professionnelles :
    Activité : responsable R&D vidage de truites

    Informations forums :
    Inscription : Novembre 2010
    Messages : 3 035
    Points : 8 400
    Points
    8 400
    Par défaut
    Citation Envoyé par jack-ft Voir le message
    Lorsqu'il n'y en a qu'une (comme pour la factorielle), l'algo peut la plupart du temps être transformé en récusivité terminale voire en simple itération (donc pas besoin de pile).
    oui, c'est ce que font certains compilateurs d'ailleurs, ils "transforment" ou "considèrent" les fonctions récursives terminales comme des itérations (c'est le cas du compilateur Scheme par exemple: "Ce que dit très précisément la norme de Scheme, c'est qu'une récursivité terminale sera traitée comme une itération, donc sans pile.")

    du coup est-ce qu'on considère toujours qu'il s'agit d'un code récursif ? (le code en lui même ne change pas, il s'appelle bien lui même etc. mais le code généré, le traitement lui est une itération)

    • si "oui", ça veut dire que la récursion tient à la forme du code, donc tout code qui fait mine de s'appeler lui même, y compris un 10 goto 10, est considéré comme récursif, une forme particulière de récursion, c'est ce que dit Flodelarab

    • si "non", ça veut dire que la différence entre l'itération et la récursion tient bel et bien à la notion de pile, la seule différence entre une itération et une fonction récursive terminale étant que l'une sort directement par le dernier appel tandis que l'autre remonte toute la pile d'appel avant de sortir, et dans ce cas ça veut dire qu'autant le code avec source $0 peut facilement être considéré comme récursif compte tenu du fait que bash doit pouvoir revenir à la suite du premier appelant pour sortir, autant le code avec exec $0 ne l'est pas, puisqu'il n'empile rien, quand bien même il s'agit du même processus tout du long

    mieux encore; le source $0 étant la dernière instruction, si bash est suffisament intelligent il peut éventuellement envisager de dérouler le tout comme une itération lui aussi (du coup pour avoir la réponse à la question initiale posée par N_BaH, il va falloir se palucher les sources de bash, qui est chaud ? )

    finalement ça revient essentiellement à une question de fond et de forme...

Discussions similaires

  1. [PHP 5.3] Récursivité, pas de retour
    Par Lost In Translation dans le forum Langage
    Réponses: 1
    Dernier message: 21/04/2010, 12h20
  2. Programmer encore en VB 6 c'est pas bien ? Pourquoi ?
    Par Nektanebos dans le forum Débats sur le développement - Le Best Of
    Réponses: 85
    Dernier message: 10/03/2009, 15h43
  3. Probleme récursivité pas si récursive que ça
    Par kirasakuya dans le forum C#
    Réponses: 1
    Dernier message: 17/07/2008, 17h02
  4. Pas de fork sous Windows?
    Par chezjm dans le forum POSIX
    Réponses: 8
    Dernier message: 11/06/2002, 13h15

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo