• # Loupé

    Posté par  . Évalué à -2.

    Sans pile c’pas récursif, mais vulgairement itératif.

    • [^] # Re: Loupé

      Posté par  (site web personnel) . Évalué à 2.

      • [^] # Re: Loupé

        Posté par  . Évalué à 1.

        Haha ! suffit de lire l’exemple, la factorielle… qui s’implémente trivialement en itératif.

        • [^] # Re: Loupé

          Posté par  (site web personnel, Mastodon) . Évalué à -2.

          De toute façon, toute personne qui écrit une méthode récursive a intérêt à l’accompagner d’un commentaire qui justifie pourquoi c’est une bonne idée de faire ça, tellement ça pose de problèmes (taille de pile à l’exécution, lisibilité, maintenance…).

          La connaissance libre : https://zestedesavoir.com

          • [^] # Re: Loupé

            Posté par  (site web personnel) . Évalué à 2.

            t'a jamais vu de code en OCaml/ask hell(Y'a une faute dans le nom ?)/lisp… ?

            Certains langages assure que la récursion terminal, s'optimise pour pas justement casser la pile.

            Mais oui, si on parle de C/java/Rust/python ou autre je suis d’accord.

            • [^] # Re: Loupé

              Posté par  (site web personnel, Mastodon) . Évalué à 0. Dernière modification le 18 août 2023 à 10:51.

              Ça ne résous pas les problèmes de lisibilité et de maintenance (qui sont les plus importants sur du code "de production", destiné à être conservé et maintenu longtemps).

              La connaissance libre : https://zestedesavoir.com

              • [^] # Re: Loupé

                Posté par  (site web personnel) . Évalué à 4.

                Mais la lisibilité, c'est énormément lier aux pratique utiliser dans un langages de programmations, et si t'a de la récursion dans toutes t'a lib standard (genre en ocaml), que la moitiés des idioms de ton languages utilise de la récursion, tu va justement plus rebuter les gents qui sont habituer à coder en fonctionnel, en leur imposant une boucle, la ou la plupart des dev auraient mit de la récursions.

            • [^] # Re: Loupé

              Posté par  (site web personnel, Mastodon) . Évalué à 9. Dernière modification le 18 août 2023 à 13:23.

              Mais oui, si on parle de C/java/Rust/python ou autre je suis d’accord.

              Je peux pas dire pour ta liste complète, mais en C (et C++) au moins, les compilateurs sont capables de reconnaître et optimiser des fonctions récursives terminales depuis très longtemps (tu trouves des références à cela sur des liens vieux de plus de 10 ans). 🙂

              Cela inclut au moins les principaux compilateurs (GCC, clang, etc.).

              En plus, je découvre même un nouvel attribut musttail dans Clang (et discuté pour GCC) super intéressant car il permet de forcer les optimisations en récursion terminale même si on désactive les autres optimisations de manière globale à la compilation.

              Je transmets la nouvelle de cet attribut pour info et parce que je le découvre moi-même, mais l'optimisation de récursion terminale existait déjà en C, et ce depuis longtemps. Je le répète (allez pas dire que c'est apparu en 2021! La seule différence, c'est que maintenant on peut informer le compilateur pour s'assurer que le code est optimisé, alors qu'avant on devait se fier à la capacité du navigateur à détecter les récursions terminales, ce qui marchait bien déjà). Perso j'en utilise régulièrement.

              Enfin bon, la récursion terminale, c'est bon. Mangez en! C'est une bonne pratique de développement.

              De toute façon, toute personne qui écrit une méthode récursive a intérêt à l’accompagner d’un commentaire qui justifie pourquoi c’est une bonne idée de faire ça, tellement ça pose de problèmes (taille de pile à l’exécution, lisibilité, maintenance…).

              Pour la "taille de pile", comme dit juste au dessus, ce n'est pas un problème pour quiconque utilise un langage ou compilateur moderne (cela inclut le C). Au contraire, c'est justement en écrivant du code récursif terminal qu'on règle ce genre de problèmes quand ils adviennent.

              Pour la lisibilité et maintenance… je sais pas ce que tu développes, mais je ne suis absolument pas d'accord avec ce commentaire. Au contraire, du code récursif est souvent très compréhensible et justement a un pouvoir d'auto-documentation du code grâce au nom de fonction qui rend l'algorithme souvent encore plus lisible et évident.

              Comme dit plus haut, j'utilise régulièrement des fonctions récursives, et j'essaie d'ailleurs en général de les rendre terminales.

              Il y a des cas qui se prêtent plus à de simples boucles itératives, mais aussi beaucoup de cas où les fonctions récursives aident énormément (à la simplicité du code, sa logique, en rendant le code vraiment clair et lisible, et enfin bien sûr par sa capacité à être très efficace grâce aux optimisations dont les compilateurs sont capables de nos jours).

              Enfin bon, c'est assez étonnant parce que pour moi, c'est l'inverse de ce que tu dis! 😜

              Film d'animation libre en CC by-sa/Art Libre, fait avec GIMP et autre logiciels libres: ZeMarmot [ http://film.zemarmot.net ]

              • [^] # Re: Loupé

                Posté par  (site web personnel) . Évalué à 2.

                Je connaissaient pas musttail, et je te remercie de ton commentaire, parce-que ça va contredire ce que je vais dire, mais dans les cas sans musttail même si les compilateur gére la récursion terminal, ça reste au bon vouloir des optimisation, et si on sait que l'on peu exploser ça stack avec un récursion, je l'utiliserais pas. surtout que avec un -O0, bah ça va pas optimiser, et -O0, ça reste bien pratique pour du debug.

                Après pour moi le cas de la lisibilité, c'est vraiment un question de connaître les idiomes du code qu'on patch, et s'y adapter.
                La on parle de récursions, mais ça peu s'adapter a n'importe quel code. C'est toujours embêtant d'expliquer à quelqu'un qui rentre dans un code libre et essaye de modifier le code pour qu'il lui convienne mieux en appliquant par exemple, ce qu'on lui a apprit a l'école au détriment du style déjà utilisé dans le projet, qu'il ferais mieux de juste imiter le coding style des autres fonctions du projets.

                • [^] # Re: Loupé

                  Posté par  (site web personnel, Mastodon) . Évalué à 5. Dernière modification le 18 août 2023 à 15:16.

                  ça reste au bon vouloir des optimisation, et si on sait que l'on peu exploser ça stack avec un récursion, je l'utiliserais pas.

                  C'est vrai. C'est une bonne remarque. J'espère donc que cet attribut va se répandre, et notamment arriver chez GCC. Je vois que ça a été discuté et notamment il est expliqué qu'ils ont déjà toute l'infra mais n'ont pas d'attribut exposé (dans la discussion, certains se demandaient comment gérer cela pour les architectures où c'est plus compliqué à assurer, bien que j'ai l'impression qu'au final, il n'y ait pas vraiment de cas absolument impossible à gérer). Quelqu'un dans la discussion l'a même implémenté en plug-in GCC mais j'ai pas l'impression que c'est arrivé dans l'implémentation standard (en tous cas, mes recherches ne donnent rien).

                  Ensuite pour modérer un peu, on ne fait pas forcément des récursions pour des choses qui sont suffisamment énormes pour exploser la stack (même si on peut ne pas connaître la fin d'une récursion avant de la commencer). Souvent, on peut faire des récursions pour des choses qui sont habituellement de taille raisonnable (bien que si cela dépend de données utilisateurs par exemple, cela peut aussi être un vecteur d'attaque; enfin bon, c'est du cas par cas).
                  Mais oui, c'est sûr que dans certains cas, je comprends que cela puisse être une limitation si on a besoin de compiler sans optimisation et si on n'a pas accès à l'attribut explicite musttail.

                  Film d'animation libre en CC by-sa/Art Libre, fait avec GIMP et autre logiciels libres: ZeMarmot [ http://film.zemarmot.net ]

          • [^] # Re: Loupé

            Posté par  . Évalué à -5.

            C’est un drame les appels récursifs : on présente ça aux étudiants dans le cadre de la formation. Soit. Mais ça devrait être banni d’un contexte professionnel ; pour un ingé qui a un peu de bouteille, c’est le minimum syndical de savoir coder un algo récursif avec sa propre pile (et pas celle du langage, car rien ne le justifie — quand il est impératif).

            • [^] # Re: Loupé

              Posté par  . Évalué à 8.

              C'est un drame de se dire que le codeur de base fait mieux que le compilo pour optimiser ;) Ce dernier fait généralement mieux que nous, et des choses qui s'expriment simplement en récursif deviennent un enfer en itératif.

              Il faut privilégier la simplicité d'écriture, sauf cas critique (identifié comme tel, pas pifométré); et essayer de tordre le code parce qu'un illuminé a dit pas de 'machin' pour dérouler l'algo ou le tourner différemment rend un code difficile à comprendre, bourré de cas d'erreurs, et est généralement bien plus compliqué que la façon simple.

              Il ne faut pas décorner les boeufs avant d'avoir semé le vent

              • [^] # Re: Loupé

                Posté par  . Évalué à 0.

                et des choses qui s'expriment simplement en récursif deviennent un enfer en itératif.

                Non. C’est juste que tu n’as pas appris et que tu n’as pas l’habitude. C’est tout mon propos. Problème de formation. Un code récursif n’explicite pas les éléments de ta pile et peut poser quelques inconvénients à l’implémentation (variable locales & arguments sont confondus avec les éléments de ta pile, obligation souvent d’avoir une fonction chapeau pour initier la récursion).

                Un algo récursif définit explicitement les éléments de ta pile. En C par exemple j’ai pris pour habitude d’avoir une struct el _stack[SIZE], *stack=_stack;. Mon struct el est explicite donc plus lisible, d’autant plus qu’il va être souvent non spécifique (dans le parcours d’un arbre/graphe par exemple c’est les node du graphe). Empiler et dépiler sont des opérations on ne peut plus simple que stack++ ou stack-- où tu transmet/alimente les valeurs nécessaires (arguments et valeur de retour sur la pile) et contrôle les dépassements avec la possibilité d’allocation dynamique (l’empilage et le dépilage sont implémentées comme des petites macro ou fonction inline).

                Tu as aussi une grosse méconnaissance des langages type C. Car c’est exactement ce qu’ils mettent un œuvre, un algo récursif avec comme pile la fameuse “call stack”. Donc rien d’insurmontable.

                L’appel à une fonction ce n’est rien d’autre qu’un empilage/rebouclage.
                Le retour d’une fonction un dépilage. Sans avoir rien à tordre, ton appel récursif est trivialement transposable en un pseudo-code récursif de la forme —très— universelle suivante :

                
                appel:
                  ...
                
                retour:
                  ...
                
                decision:
                  si appel récursif:
                  {
                    empiler
                    goto appel
                  }
                  sinon:
                  {
                    dépiler
                    si la pile est vide on a terminé.
                    sinon goto retour
                  }
                ...
                

                Note qu’on fait sans les goto en général, mais c’est pour montrer qu’on peut être plus universel encore que l’appel récursif — car là où un retour à l’appelant suit forcément l’appel à une fonction (le pointeur d’instruction est mis sur la pile puis dépilé), le goto/label est bien plus souple (la forme que je présente n’est pas possible avec une fonction récursive — il faut tordre l’algo).

                C'est un drame de se dire que le codeur de base fait mieux que le compilo pour optimiser

                J’aimerai sincèrement que soit faite la démonstration que le compilo est capable de distinguer très exactement la pile de ton algo de la call stack et de les séparer. S’il y arrive, la call stack ne doit plus être manipulée lors de la récursion et c’est tout l’enjeu. En commençant par bien distinguer les arguments de ta fonction récursive, entre ceux qui participent à la récursivité de ceux qui sont invariants dans la récursion, ensuite en étant capable de faire sauter la limitation en taille de la call stack, idem les variables locales qui n’ont pas forcément à être empilées.

                Et pas uniquement dans le cas de la mal nommée “récursion” terminale (qui est toujours trivialement transposable en itératif ceci dit en passant).

                Et non c’est pas du tout lisible : si je lis un appel récursif je m’attend à un algo récursif, pas un truc oui-mais-en-fait-non. Il s’agit aussi d’évaluer la complexité et la performance d’un bout de code (itératif : je sais que je suis en O(𝑛), récursion je m’attends à un truc du genre O(𝑛log(𝑛))), et de ne pas se rajouter de la charge mentale (il est beaucoup plus difficile d’appréhender le comportement d’un code buggé qui a une pile, donc j’aime savoir si la pile est vraiment justifiée).

                Qui plus est il ne s’agit pas d’optimiser, mais précisément de ne pas créer un code inutilement complexe pour le compilo. En plus de ça, dès que tu vas vouloir faire des algos sur des données un minimum couillues tu vas vouloir contrôler ta taille de pile (donc exit la call stack).

                • [^] # Re: Loupé

                  Posté par  . Évalué à 6.

                  bien maintenant fait moi les tours de hannoï en itératif, on va rigoler un peu :)

                  C'est 3 lignes en récursif ;)

                  de même en caml la gestion des listes se fait aisément et de manière lisible; je ne compte plus le nombre de fois où j'ai du passer après quelqu'un qui s’empêtrait dans de l'itératif alors que le cas ne s'y prétait pas (typiquement parcours d'arbre en profondeur)

                  En gérant toi même la pile tu force la main au compilo, je n'ai JAMAIS eu de stack overflow sur de appels récursif se se plantant pas sur la condition d'arrêt. Et ton système il fera juste un out of memory à la place; risquant de faire tuer des voisins un peu trop gourmand.

                  Il ne faut pas décorner les boeufs avant d'avoir semé le vent

                • [^] # Re: Loupé

                  Posté par  . Évalué à -1.

                  J’ai oublié de signaler. La call stack utilise une pile qui est implémentée dans le CPU, avec des instructions spécifiques si je ne m’abuse. Il y a effectivement possiblement un gain de performance à aller gratter de ce côté là.

                  MAIS.

                  Ça ne compense pas, très largement, l’overhead de la call stack (on empile/dépile tout le contexte d’exécution de la fonction en lieu et place des seules données propres à la récursion). Si je présente un algo avec des goto c’est aussi pour mettre en lumière cet aspect : l’instruction pointer par exemple va être empilé à tort lors d’un appel récursif (c’est le principe même d’une call stack).

                  • [^] # Re: Loupé

                    Posté par  . Évalué à 7.

                    ton pseudo code est une horreur à lire, à suivre et donc à maintenir; en utilisant des goto, tu as tendance à pulvériser les exécutions prédictives pour au final faire un truc qu'un compilo peut faire de lui même;

                    Dans l'immense majorité des cas, il vaut mieux laisser le compilo faire de lui même les optimisation avec des schémas traditionnel simple; en essayant de faire intelligent, tu le court-circuite; tu ajoutes de l'allocation dynamique pour un gain nul. Tu es typiquement dans ce cas la : PrematureOptimization

                    Il ne faut pas décorner les boeufs avant d'avoir semé le vent

                    • [^] # Re: Loupé

                      Posté par  . Évalué à 3.

                      ah oui, j'ajouterai aussi que la condition de fin de récursivité est plus lisible si c'est les premières lignes (exit early); et si tu est tant que ça obsédé par les performances tu peux utiliser les indication unlikely ou autre

                      voici un petit code simple :

                      int count(int n) {
                        if( n <= 0 ) return 0;
                        if (n%10000 == 0) std::cout << n << " ";
                        return 1 + count(n-1);
                      }
                      
                      int main(int argc, char *argv[]){
                        int n;
                        n = std::atoi(argv[1]);
                        std::cout << count(n) << std::endl;
                        return 0;
                      }

                      à compiler avec -O3 pour que le compilo vire la récursivité

                      g++ -O3 countr.cc -o countr
                      ./countr 1000000000 
                      [...] 90000 80000 70000 60000 50000 40000 30000 20000 10000 1000000000

                      sans le -O3 j'ai évidemment un stack overflow ;)

                      maintenant je t'invite à coder à ta façon ces 3 lignes de codes d'appel récursif; techinquement j'aurais pu en mettre que 2, mais la centrale sert de s'assurer de pas avoir une optimisation trop agressive du genre int a(int n) {return n;}

                      Une fois que tu as fais ce petit morceau de code va trouver un codeur et demande lui ce que ça fait. puis va voir un autre codeur avec les 3 lignes pour la même question.

                      Il ne faut pas décorner les boeufs avant d'avoir semé le vent

                      • [^] # Re: Loupé

                        Posté par  . Évalué à 3.

                        sans le -O3 j'ai évidemment un stack overflow ;)

                        Elles sont hyper agressives les optimisations de gcc ! Même sans récursion terminale, il s'en sort. Si je fais ça en OCaml, je me paye systématiquement un stackoverflow sur de grandes entrées.

                        D'ailleurs, sur ta réponse précédente tu lui reprochais de faire de l'optimisation prématurée, mais il n'y avait aucune optimisation, et c'est bien là le problème : à chaque appel récursif, il empile et ne dépile qu'à la fin de la récursion, et donc il y a stackoverflow à tous les coups. ;-)

                        Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

                        • [^] # Re: Loupé

                          Posté par  . Évalué à 3.

                          Justement si, une optimisation sur la pile d'appel car il estime qu'on risque de partir en stack overflow, ou qu'on perd trop de temps en changement de contexte. Je ne dis pas que ces problèmes sont inexistants, juste que dans la majorité des cas le compilo fait très bien les optimisations qui vont bien, le tout en respectant (généralement mieux que ce que le commun des mortels) les spécificité des processeurs modernes (exécution prédictive, pipeline, cache…)

                          Je ne dis pas qu'il faut faire du récursif, souvent on peur remplacer par de l'itératif sans que ça alourdisse le code, mais remplacer tout appel récursif, juste par principe, avant même qu'un problème ait été levé, le tout via des solutions lourdes et compliqué rends rapidement le code visé difficile à maintenir.

                          Il ne faut pas décorner les boeufs avant d'avoir semé le vent

                          • [^] # Re: Loupé

                            Posté par  (site web personnel) . Évalué à 4.

                            sauf que un code qui marche avec -O3, mais pas sans ça, personnellement, j’appelle ça un code cassée.

                            Pas qu'il ne fasse jamais faire du récursive, mais s'appuyer sur l’hypothèse que le compilateur va optimiser ton code pour qu'il marche, font pleurer les heures que j'ai passer à utiliser/modifier tinycc.

                            • [^] # Re: Loupé

                              Posté par  . Évalué à 2.

                              oui enfin sans opti il fonctionne quand même jusqu'à 261789; ça suffit amplement pour les cas de tests ;) (oui ça plante à 261790)

                              je n'ai jamais eu besoin d'une telle profondeur.

                              Il ne faut pas décorner les boeufs avant d'avoir semé le vent

                          • [^] # Re: Loupé

                            Posté par  . Évalué à 3.

                            Justement si, une optimisation sur la pile d'appel car il estime qu'on risque de partir en stack overflow, ou qu'on perd trop de temps en changement de contexte.

                            Je ne vois pas trop cela dans son pseudo-code : il teste si l'appel est récursif et il empile, puis ne dépile que dans le cas contraire. On risque le débordement de pile. Mais c'est peut être moi qui ne comprend pas ce qu'il veut faire, je trouve qu'il ne s'exprime pas clairement.

                            Après ce n'est pas tant une question d'optimisation, contrairement à ton exemple. Pour moi, une fonction récursive terminale doit être compilée en consommant un espace constant sur la pile, sinon le compilateur est buggé. Je ne considère pas cela comme une optimisation mais comme une obligation sur le schème de compilation à utiliser.

                            Ton exemple est simple à écrire comme il faut, sans compter sur une optimisation du compilateur. Je le fais en OCaml :

                            let count n =
                              let show i = if i mod 10_000 = 0 then (print_int i; print_newline ()) in
                              let rec loop acc = function
                                | 0 -> acc
                                (* ici l'appel récursif est terminal *)
                                | i -> show i; loop (acc + 1) (i - 1)
                              in loop 0 n
                            ;;

                            Le code récursif, correctement compilé, est équivalent à celui-ci avec un boucle for :

                            let count_for n =
                              let show i = if i mod 10_000 = 0 then (print_int i; print_newline ()) in
                              for i = n downto 0 do
                               show i
                              done;
                              n
                            ;;

                            Quelque soit le code choisi, il n'y a aucun risque de saturer la pile.

                            Je ne dis pas qu'il faut faire du récursif, souvent on peur remplacer par de l'itératif sans que ça alourdisse le code, mais remplacer tout appel récursif, juste par principe, avant même qu'un problème ait été levé, le tout via des solutions lourdes et compliqué rends rapidement le code visé difficile à maintenir.

                            Comme dit par uso dans le fil, cela dépend du langage utilisé et de ses idiomes. L'écriture de code récursif est tout un art. En OCaml, la plupart du temps on ne peut écrire du code que de manière récursive. Par exemple, la fonction qui itère une autre fonction (par effet de bords) sur les listes ne peut être écrite qu'ainsi :

                            let rec iter f = function
                              | [] -> ()
                              | hd :: tl -> f hd; iter f tl
                            ;;

                            Exemple d'usage :

                            List.iter print_int [1; 2; 3];;
                            (* retour de l'appel *)
                            123

                            La fonction est terminale récursive et aura un code compilé équivalent à celui avec une boucle for ou while d'un langage impératif.

                            Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

                            • [^] # Re: Loupé

                              Posté par  . Évalué à 3.

                              Après ce n'est pas tant une question d'optimisation, contrairement à ton exemple. Pour moi, une fonction récursive terminale doit être compilée en consommant un espace constant sur la pile, sinon le compilateur est buggé.

                              Justement, lui le fait à la place du compilo, la pile dont il parle est une structure gérée par lui, manuellement. Bref il fait le travail que tu estime être du domaine du compilateur

                              Comme dit par uso dans le fil, cela dépend du langage utilisé et de ses idiomes.

                              oui ça dépend évidemment des langages, on ne code pas en COBOL comme on code en OCaml, et on ne code pas en Perl comme en lisp.

                              Il ne faut pas décorner les boeufs avant d'avoir semé le vent

                              • [^] # Re: Loupé

                                Posté par  . Évalué à 3.

                                Bref il fait le travail que tu estime être du domaine du compilateur

                                J'avais bien compris qu'il voulait gérer sa pile tout seul mais, de ce que je comprends, il s'y prend n'importe comment. Tel était mon reproche. ;-)

                                C'est comme pour son calcul de complexité, on ne sait pas trop quel algorithme il a en tête. Par exemple, le type des ensembles, en OCaml, est implémenté par des arbres binaires équilibrés. Certaines fonctions de parcours, qui sont toutes récursives (on ne peut faire autrement dans le langage), ne sont pas terminales et n'ont pas besoin de l'être. Elles occupent sur la pile un espace linéaire par rapport à la hauteur de l'arbre, hauteur qui est en log (n) (et non n log (n)) où n est la taille de l'ensemble : le risque de débordement est quasi nul. On pourrait les écrire en CPS (continuation passing style) pour occuper un espace constant avec des récursives terminales, ce qui reviendrait à réifier la pile sur le tas (un peu comme greendev), mais ce serait moins efficaces et cela sans réelles raisons.

                                Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

                      • [^] # Re: Loupé

                        Posté par  . Évalué à -2.

                        sert de s'assurer de pas avoir une optimisation trop agressive du genre

                        Tu te rends compte que tu as réussi à écrire un simple compteur d’une manière bien tordu (et bien obfusquée), et que tout ce que fait ton compilo c’est de dénouer le sac de nœud qui te tiens lieu de pensée ?

                        \left(u_n = u_{n-1} + 1 \land u_0 = 0\right) \Rightarrow u_n = n

                        C’est ce que ton compilo fait (au mieux), de ton propre aveux. Pour trouver ça plus simple à lire que int a(int n) {return n;} t’es payé à la ligne de code, c’est pas possible autrement !

                        • [^] # Re: Loupé

                          Posté par  . Évalué à 6. Dernière modification le 22 août 2023 à 07:57.

                          non j'illustre par un cas simple; tout comme on adore donner la factorielle pour une illustration de la récursivité alors que ça se fait tout aussi bien en itératif, ou même avec fact(n).

                          Si le code est compliqué pour un bête compteur, qu'est ce que ça donne lorsque la complexité augmente?

                          Il ne faut pas décorner les boeufs avant d'avoir semé le vent

                    • [^] # Re: Loupé

                      Posté par  . Évalué à -10.

                      Rhô ça sert à rien de faire l’intelligent, la réalité c’est que vous savez pas coder un algo récursif et que vous vous cachez derrière des choses que vous maîtrisez pas. Pour preuve, j’ai bien signalé que les goto n’était pas obligatoires (dans la très grande majorité des cas je m’en passe), j’ai aussi dit que je présentais le cas le plus général (donc pas une optimisation…).

                      Mais bon c’pas grave continue comme ça. C’pas grave hein si t’es pas bon en algorithmie, t’as l’droit. Pas besoin de s’inventer une excuse.

          • [^] # Re: Loupé

            Posté par  (site web personnel) . Évalué à 3.

            Ça veut dire qu'en pratique, devnewton aurait dû écrire un journal avec commentaire plutôt qu'un lien ;)

            Et ça aurait été plus original.

          • [^] # Re: Loupé

            Posté par  (site web personnel, Mastodon) . Évalué à 2.

            Au fait, quand j’écris :

            toute personne qui écrit une méthode récursive a intérêt à l’accompagner d’un commentaire qui justifie pourquoi c’est une bonne idée de faire ça

            Ça veut juste dire ce qui est écrit, à savoir : que quand on écrit du code récursif, il faut être capable de l’expliquer et de le justifier. Et donc, de l’utiliser si c’est le code le plus efficace (le plus logique, lisible, performant, tout ça à la fois…) – par exemple si on doit faire un traitement dont la logique fonctionnelle est récursive, c’est probablement une bonne solution.

            Ça ne signifie absolument pas qu’il faut s’interdire de faire du code récursif.

            Non parce que quand je vois les réactions, c’est ce que certains ici semblent avoir compris.

            La connaissance libre : https://zestedesavoir.com

            • [^] # Re: Loupé

              Posté par  (site web personnel) . Évalué à 2.

              Mais le truck, c'est que dans un code qui utilise un langages fonctionnel, tu risque de voir plus de récursion que de boucles.

              Si quelqu'un viens te dire:

              toute personne qui écrit une while ou un for à intérêt à l’accompagner d’un commentaire qui justifie pourquoi c’est une bonne idée de faire ça

              Peu être que tu va te dire que c'est un peu abusé. (ceci dit ça m'étonnerais pas que des dev haskell aient déjà dit ce genre de choses)
              Et je peu rejoindre que sur du C, justifier que l'on risque pas d'exploser la stack est une bonne choses. (et utiliser musttail je considère ça comme du self documentes code donc pas forcement besoins d'un autre commentaire)

              Ce qui fait réagir, c'est de pas l'avoir dit dans le contexte d'un langage particulier.

              • [^] # Re: Loupé

                Posté par  . Évalué à 3.

                Ce qui fait réagir, c'est de pas l'avoir dit dans le contexte d'un langage particulier.

                Moi qui n'écris pratiquement presque que du OCaml, j'aurais pu écrire ton inversion de demande de légitimité. Si on prend le vénérable taptempo en OCaml, le premier qui vient me demander de justifier ma boucle loop récursive par rapport à une immonde boucle while risque de regretter sa demande de justification. ;-)

                Les fonctions récursives c'est le pendant calculatoire des constructions par récurrence et du raisonnement par récurrence. Le plus simple d'entre eux étant le raisonnement par récurrence sur les nombres entiers (représentés de manière unaire) :

                • si une propriété est vraie de 0 ;
                • si elle est vraie de n alors elle est vraie de n + 1 ;
                • alors elle est vraie de tout entier.

                Il existe une autre version de l'hypothèse de récurrence qui devient :

                • si elle est vraie de tout entier ≤ n alors est vraie de n + 1

                Dans la première formulation la taille de l'hypothèse est constante (le cas n), dans la seconde elle croît linéairement avec n (la conjonction de tous les cas jusqu'à n).

                Dans le premier cas, on a une récursion terminale qui utilise un espace constant sur la pile; dans le second l'espace consommé croît linéairement avec la taille de l'entrée, on risque le débordement de pile.

                Les entiers unaires n'étant rien d'autres que des listes chaînées, le module des listes de la bibliothèque standard de OCaml contient une grande quantité de fonctions récursives (dont certaines ne sont pas terminales récursives).

                Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

  • # Cinq ans et demie de retard

    Posté par  (site web personnel, Mastodon) . Évalué à 10. Dernière modification le 17 août 2023 à 23:04.

    Bravo, tu viens de refaire la blague du 7ème lien posté sur LinuxFR :

    https://linuxfr.org/users/roduit/liens/lien-recursif

    (Oui, j’ai une bonne mémoire, mais seulement pour les trucs inutiles).

    La connaissance libre : https://zestedesavoir.com

  • # pas totalement récursif...

    Posté par  . Évalué à 2.

    on ne peut moinsser voter qu'une seule fois malheureusement…

    « Le pouvoir des Tripodes dépendait de la résignation des hommes à l'esclavage. » -- John Christopher

  • # J'ai explosé ma stack...

    Posté par  . Évalué à 3.

    … car il n'y a pas de condition de sortie !

  • # Déjà fait

    Posté par  (Mastodon) . Évalué à 3.

    https://linuxfr.org/users/gbetous/liens/qu-est-ce-que-la-recursivite

    En théorie, la théorie et la pratique c'est pareil. En pratique c'est pas vrai.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.