Discuter:Algorithme récursif

Un article de Wikipédia, l'encyclopédie libre.

Sommaire 1 Factorielle 2 Le deuxieme exemple ? 3 Algorithme en Visual Basic non-récursif et carrément FAUX 4 Algorithme récursif pour résoudre un problème parfaitement accessible à une solution itérative?! 5 Le théorème de correction 6 Récursivité

[modifier] 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)

[modifier] 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

[modifier] 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)

[modifier] 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)

[modifier] 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 une fonction récursive définie sur un ensemble .

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)

[modifier] 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ématciens. Pierre de Lyon 28 août 2006 à 17:24 (CEST)