Discussion:Algorithme récursif

Factorielle

Qu'est ce qui se passe si j'appelle factorielle avec 0 comme parametre? D'apres cet algorithme,
factorielle(0) egale 0 * factorielle (-1)...

Soit on a une erreur de syntaxe parce que le type entier est defini comme ensemble des nombres positifs, soit on court vers une recursion infinie. Aucune des deux ne correspond au resultat escompte.

or factorielle(0) egale 1

Ma proposition serait:

factorielle(entier k):entier

si k<0 renvoyer 0 (pour le cas ou la fct. serait appellee avec un neg. et que le type entier comprrendrait bel et bien les negatifs...)

si k=0 /* premiere condition d'arret pour le cas special factorielle(0)*/

 alors renvoyer 1

sinon si k=1 /* deuxième condition d'arret, inutile en fait */

 alors renvoyer 1

sinon renvoyer k * factorielle(k-1)

fsi

Tcheer 19 avr 2004 à 16:31 (CEST)

Il est vrai que la fonction a une petite erreur : il faut remplacer la condtion "si k=1" par "si k=0". La fonction factorielle n'est pas definie pour les nombres negatifs. Traroth 19 avr 2004 à 16:40 (CEST)

Traroth, ta modification fait que fact(n) = 0 pour tout n, je remplace "si k = 0 retourner k" par 'si k = 0 retourner 1' phe

Non. Si k=0 alors retourner 1. Donc 0! = 1 Traroth 19 avr 2004 à 16:59 (CEST)

Heu, c'est exactement ce que je dis, la version que tu as commit contenait une erreur de typographie

si k=0 alors renvoyer k <--- donc retourne 0 et fact(x) == 0 avec cette algo, voir historique, vu que c'est une erreur de typographie, j'aurais du corriger sans le signaler probablement.

phe 21 avr 2004 à 18:17 (CEST)

Le deuxieme exemple ?

Il est recursif de nul par le deuxieme exemple, c'est un algorithme simple qui n'a rien à voir du tout avec le premier exemple mis à part qu'il résoud le meme probléme.

enfin ca reste mon avis et je suis trés heureux de le partager

Algorithme en Visual Basic non-récursif et carrément FAUX

L'algorithme en Visual Basic n'est pas seulement non-récursif (mais itératif), il est aussi carrément FAUX, ne donnant le résultat correcte pour aucune valeur du paramètre. Soit la lecture avec un minimum d'attentivité et de compréhension, soit un essai simple avec n'importe quelle valeur de départ le met au jour :-( la valeur de ce programme est donc moins que nulle. — non, mes amis, comme ça, nous ne réussirons jamais à écrire une encyclopédie, hélas. — Nol Aders 28 novembre 2005 à 12:36 (CET)

Algorithme récursif pour résoudre un problème parfaitement accessible à une solution itérative?!

Hélas, c'est un mauvais exemple pour illustrer la récursion, parce que c'est trop simple, étant donné que la factorielle d'un nombre (ne pas trop élevé comme <=170) se calcule encore plus simplement par moyen d'une boucle toute simple (pour varier en langage Java):

public static long factorielle(short n) { long fact=1; for (short i=2;i<=n;i++) fact*=i; return fact; }

S'il existe une solution itérative simple, en général, celle-ci est préférable aux solutions récursives, parce qu'elle est plus facile à comprendre et à corriger.

Parmi les problèmes pour lesquels une solution récursive est raisonnable sont le fameux tri rapide (aussi connu par sa désignation anglaise Quicksort), le fameux tri fusion (aussi connu par sa désignation anglaise Mergesort), les fameux Tours de Hanoï, le fameux Retour sur trace (le Backtracking anglais), le parcours d'un arbre, dessin de beaucoup de figures fractales comme le triangle de Sierpinski, etc.

On présente mal un principe puissant en l'illustrant à l'attaque de problèmes trop banaux pour jouir de la puissance du principe.

— Nol Aders 27 décembre 2005 à 03:18 (CET)

Tu as raison, c'est pourquoi je me suis permis de construire un exemple préliminaire qui, outre qu'il n'est pas issu directement des mathématiques, n'a pas de solution itérative immédiate, c'est-à-dire qui n'imiterait pas une solution récursive. Il s'agit bien évidemment du problème de la génération des permutations. Pierre de Lyon 26 juillet 2006 à 13:24 (CEST)

J'ai envie de traiter un exemple mathématique archétypique, à savoir le nombre de décompositions d'un entier naturel en au plus n sommants. Qu'en pensez-vous? Pierre de Lyon 26 juillet 2006 à 14:29 (CEST)

Finalement, je me suis lancé. Pierre de Lyon 27 juillet 2006 à 00:26 (CEST)

Le théorème de correction

Tel qu'il est, il est mal formulé. Quand on travaille avec un ordre bien fondé général, il n'y a pas à parler des cas de base. La règle est plus simple (a écrire et à prouver, peut-être pas à comprendre pour un humain éduqué dans l'itératif). Pierre de Lyon 26 juillet 2006 à 13:30 (CEST)

De plus il y a une confusion entre la définition et la fonction. La phrase

• Soit $f\,$ une fonction récursive définie sur un ensemble $A\,$.

ne veut rien dire puisque précisément ont veut démontrer qu'une telle fonction existe en démontrant sa terminaison.

Je propose de reprendre tout cela à zéro ou de le supprimer purement et simplement.Pierre de Lyon 22 août 2006 à 09:43 (CEST)

Récursivité

L'article récursivité, sur lequel pointe celui-ci, me semble parler du même sujet, et (attire d'ailleurs les mêmes remarques de Nol Aders). Il contient des choses très douteuses : aspects historiques (Gödel a déjà démontré ses th. d'inc. quand il rencontre Church etc.), à propos du système T ... Est-il nécessaire sous cette forme ? Ne peut-il être remplacé par celui-ci, en reprenant ce qui est correct éventuellement ?

Par ailleurs on parle aussi de récursivité dans le sens de calculabilité (une source possible d'ailleurs des confusions de l'article récursivité). L'article récursivité devrait aborder ou plutôt pointer sur les deux notions. Proz 27 août 2006 à 23:35 (CEST)

Merci de pointer sur cet article que je ne connaissais pas et qui fait double emploi avec celui-ci, en plus mauvais (me semble-t-il). Je propose qu'on en demande la suppression, puis plus tard "récursivité" pointera vers celui-ci.

Oui bien sûr, la récursivité est due à Gödel, qui est venu à Princeton en ayant déjà démontré son théorème d'incomplétude. Kleene a écouté ses exposés et rédigé ses notes, puis il a effectivement travaillé sur la récursivité.

Pierre de Lyon 28 août 2006 à 08:23 (CEST)

L'article ne me semble également clairement plus mauvais que celui-ci. D'accord pour la suppression du contenu, mais le titre devant continuer à exister. Récursivité peut soit rediriger sur fonction récursive que j'ai un peu repris hier, et qui est d'ailleurs perfectible (pour l'aspect historique j'ai cité de mémoire), soit être une page courte pointant sur celle-ci et par exemple sur calculabilité. Si nous sommes d'accord sur une solution, nous pouvons le faire nous-même, il me semble. Est-ce qu'il ne faut pas avant récupérer ici, le § "acronyme récursif", anecdotique mais amusant ? Il y a aussi une référence web (que je n'ai pas consulté) mais l'article présent n'en a aucun.

Pour la récursivité : je dirai qu'en plus les travaux des années 1930 Herbrand, Gödel, Kleene etc. portent plutôt sur l'aspect "calculabilité", l'article présent me semble destiné à aborder les choses de façon plus intentionnelle. Une présentation historique devrait être claire sur ce point. Donc il ne faut rien récupérer de l'article récursivité sur cet aspect. Proz 28 août 2006 à 10:20 (CEST)

Oui, je suggère que nous allons proposer la suppresion pure est simple de l'article récursivité, quant à celui-ci (algorithme récursif), on lui garde son aspect un peu pragmatique (intentionnel) et introductif, renvoyant à Fonction récursive pour ceux qui veulent aller plus loin.Pierre de Lyon 28 août 2006 à 11:23 (CEST)

J'ai entamé la procédure de suppression de l'article récursivité.Pierre de Lyon 28 août 2006 à 11:41 (CEST)

On est bien d'accord qu'il faudra le récréer ensuite, sous une des deux formes que je propose ? Je ne suis pas bien au courant des arcanes de wikipedia, ne suffisait-il pas de le réécrire ? Proz 28 août 2006 à 11:58 (CEST)

Moi non plus, je ne suis pas bien au courant, mais j'ai déjà demandé et obtenu la suppression d'articles pour les mêmes raisons. Si on le réécrit, on va se retrouver avec trois articles:

1. récursivité,
2. algorithme récursif
3. fonction récursive

et ça n'est pas ce que nous voulons. Pierre de Lyon 28 août 2006 à 12:32 (CEST)

Tout à fait d'accord sur le principe, je me suis peut-être mal exprimé. Une des 2 propositions que je fais est de transformer récursivité en redirection sur fonction récursive, l'autre est d'en faire une page très courte et destinée à le rester, redirigeant sur calculabilité et algorithme récursif.Proz 28 août 2006 à 15:08 (CEST)

Est-ce utile d'avoir des pages minuscules qui ne font que des renvois? Je n'ai pas de réponse. Encore que ces auiguillages devraient se trouver dans le portail logique De tout façon le processus de suppression est en route. Voyons ce qu'il donne. Je pense que de « récursivité » on devrait pouvoir aller à algorithme récursif qui est écrit pour les non mathématiciens et à fonction récursive qui est écrit pour les logiciens et les mathématiciens. Pierre de Lyon 28 août 2006 à 17:24 (CEST)

Se distinguent ainsi récursivité structurelle et récursivité numérique (ou récursivité sur les entiers)

Les nombres étant des structures spécifiques, je ne comprends pas cette phrase.--Pierre de Lyon (d) 1 décembre 2009 à 23:57 (CET)

Commencer par la factorielle

Je ne suis absolument pas d'accord avec ta suppression de l'exemple de la générations des permutations. La raison est que des gens à l'époque où je l'avais introduit, s'étaient du fait que l'on commençat par un exemple de mathématiques assez artificiel et desséchant à savoir la factorielle. J'avais à l'époque proposé cet exemple pour éviter de rebuter les lecteurs. Il n'y a pas TI, car c'est bien un algorithme récursif que font M. Jourdain et son professeur de philosophie. --Pierre de Lyon (discuter) 18 septembre 2018 à 10:20 (CEST)

Il est mieux de discuter ici. Tout cela est subjectif, dans un sens comme dans l'autre. Je trouve que, exprimé de manière plus simple que cela n'était fait jusqu'ici, l'exemple de la factorielle n'est pas "artificiel et desséchant" (la présentation "plus mathématique" l'était en effet, je suis d'accord), et on peut sans doute encore l'améliorer et la rendre encore plus simple.

Dans l'autre sens, et tout aussi subjectivement, je trouve l'exemple des permutations incompréhensible et trop compliqué (je n'ai pas été convaincu d'ailleurs que l'algorithme décrit "un parmi d'autre" soit correct). De plus, il n'est pas très typique de la récursion où on définit un "cas de base" simple et où on récurse, je ne vois pas clairement le "cas de base" simple dans le cas de la permutation.

Comme tout est subjectif, il faudrait sonder la communauté. Ce n'est pas moi qui avait posé le bandeau de source, ce qui veut dire tout de même que plusieurs personnes sont d'accord pour trouver que cet exemple "sort de nulle part", et que ce paragraphe attire l'attention et fait hausser ou froncer les sourcils.

Peut-être peut-on trouver un exemple plus simple que les permutations, sans être mathématique, et plus consensuel ? Qu'en pense la communauté ? Cordialement --Jean-Christophe BENOIST (discuter) 18 septembre 2018 à 10:48 (CEST)

Il y a un cas de base, puisqu'il est dit « Tout d'abord on construit toutes les permutations de la phrase vos beaux yeux -- me font mourir -- d'amour ». D'autre part, il y a deux reproches à faire aux exemples qui restent dans l'article :

1. Ils portent tous sur les nombres naturels, comme si les algorithmes récursifs ne portaient que sur les entiers. Pauvre Rózsa Péter !.
2. Ils sont tous issus des mathématiques et même plus précisément de l'arithmétique, comme si les algorithmes récursifs ne traitaient que cette partie de la science. Bonjour l'interdisciplinarité ! Pas étonnant, après cela que quand vous discutez avec un biologiste, il ignore tout de la récursivité, et je ne parle pas des économistes ! Il y a une exception notable : nos collègues linguistes connaissent ce concept, mais on leur a enlevé le seul exemple qui parle de langue.

--Pierre de Lyon (discuter) 18 septembre 2018 à 11:35 (CEST)

C'est pour cela que je disais que la solution/compromis est peut-être de trouver un exemple plus clair que la permutation, avec un cas de base plus identifiable et simple (pourquoi commencer à 3 et pas à 2 ou à 4 ?), sans porter sur des nombres naturels. Je pense sincèrement que la notion de cas de base passe totalement inaperçue dans l'exemple des permutations. L'idéal serait de trouver l'idée dans une source de manière à pouvoir le sourcer, et diminuer la subjectivité de l'estimation de la pertinence de l'exemple (si une source notable l'a donné, c'est qu'il est pertinent, par définition). --Jean-Christophe BENOIST (discuter) 18 septembre 2018 à 12:53 (CEST)

J'aurais deux propositions d'exemple : 1) Le parcours de labyrinthe. Trouver un chemin dans un labyrinthe c'est explorer toutes les directions de la case où je suis et trouver le chemin dans le labyrinthe plus petit où la direction explorée est l'entrée de ce labyrinthe. Le cas de base est quand une des directions de la case où je suis donne directement sur la sortie. 2) Bien que cela soit un exemple sur les nombres, c'est suffisamment connu pour parler à tout le monde sans ce cela soit "artificiel et desséchant" : le compte est bon. Les deux exemples sont sourçables dans www.chambily.com/recursivite/recursivite.pdf (entre autres !) Cordialement --Jean-Christophe BENOIST (discuter) 18 septembre 2018 à 14:41 (CEST)

Bonjour à vous 2, si la question est de trouver un algo récursif initial qui ne rebuterait pas les fans de maths (car à eux aussi, même s'ils peuvent faire de la prose sans le savoir, Mr Jourdain en début d'article, sur un tel sujet, peut les dissuader de lire la suite) ni non plus les biologistes voire les littéraires, je propose :

• algo permettant d'inverser une chaîne de caractères (azertyui → iuytreza), voire mieux algo qui détecte qu'une chaîne de caractères est un palindrome (Noel ↔ Leon)
• Ou pour rester en maths mais sans faire intervenir la factorielle (peu connu du grand public), ben simplement définir la multiplication que tout lecteur connaît évidemment, et avec l'algo récursif :

mult(n, 0) = 0

mult(n, p+1) = mult(n, p) + n.

Ce qui est en passant des axiomes de Peano de l'arithmétique (oui on y revient, désolé, Pierre) donc pas de TI

note : la def de l'addition est similaire mais fait intervenir la fonction +1 (successeur) inconnu du grand public et donc je n'y suis pas partisan.

Bon je vous laisse voir et décider, sachant que cette question d'intro grand public m'intéresse guère et que de plus une personne qui souhaite s'intéresser à un truc avec des mots aussi chelou que « Algorithme récursif » a sans doute un certain niveau culturel, dont en maths

Amicalement --Epsilon0 ε₀ 18 septembre 2018 à 21:43 (CEST)

J'ai développé la partie algorithme non numérique en tenant compte de vos remarques. --Pierre de Lyon (discuter) 24 septembre 2018 à 18:38 (CEST)

Merci d'avoir mis en évidence le cas de base et montré l'exemple à partir de permutations plus courtes, ce que je trouve plus clair (et du coup l'exemple qui commence à 3 permutations moins clair), mais le caractère pédagogique est tellement subjectif, et varie tellement avec les personnes.. Bon, il y en a pour tous les goûts et toutes les formes d'esprit on dirait. On verra à l'avenir si cet exemple suscite toujours des réactions en PdD ou dans l'article. Cordialement --Jean-Christophe BENOIST (discuter) 24 septembre 2018 à 21:21 (CEST)

Merci de tes encouragements. De tout façon, on ne peut pas faire l'impasse sur les algorithmes récursifs non numériques, car, vers la fin l'article, on parle de quadtree et de tri rapide, qui sont deux algorithmes non numériques importants. --Pierre de Lyon (discuter) 25 septembre 2018 à 10:35 (CEST)