Début
Appel de R
si fini reour
sinon
appel de R
si fini retour
sinon
appel de R
si fini retour
........
appel de R
si fini retour
là, on suppose qu'on a fini
donc on repasse par toutes les fonctions, et celles-ci seront supprimées de la pile.
Fin
Début
Tant que pas fini
calcul
fin tant que
fin
Ca veut dire quoi "à l'extérieur" ?D'accord mais ce que je ne comprends pas c'est pourquoi ça marche quand je fais le programme récursif à l'exterieur et qu'il prend tous les arguments et quand je le met dans le gros il ne marche plus (message d'erreur).
Dlzlogic a écrit:Ca veut dire quoi "à l'extérieur" ?
Je ne peux que conclure que mon explication n'a pas été claire.
Oh, non, je ne prends surement pas la mouche, mais l'informatique, c'est tellement compliqué que dans bien des cas, il faut "croire", et on comprendra ensuite, voire au bout de plusieurs années.Ne prenez pas la mouche, je suis très lent à comprendre !
Dlzlogic a écrit:Oh, non, je ne prends surement pas la mouche, mais l'informatique, c'est tellement compliqué que dans bien des cas, il faut "croire", et on comprendra ensuite, voire au bout de plusieurs années.
Alors, croyez moi, n'utilisez la récursivité que si c'est nécessaire.
Dlzlogic a écrit:Bonjour,
Je voudrais ajouter un petit complément à propos des fonctions utilisant la récursivité, c'est à dire une fonction qui s'appelle elle-même.
Le Fortran ne permettait pas la récursivité (Fortran IV et Fortran 77). On utilisait alors un astuce : on créait 2 fonctions A et B qui s'appelaient mutuellement. On trompait ainsi de compilateur. Mais on avait une possibilité : on pouvait créer un point d'entrée dans une fonction. Cela rendait donc la chose possible.
Je crois que cette méthode ne peut plus être employée, à cause de l'organisation différente de la mémoire. Il en résulte que la récursivité est devenue nécessaire, mais doit être utilisée avec modération.
A mon avis, pour bien la comprendre, imaginons qu'on cherche un article dans un bouquin. Cet article renvoie à un autre article du même ouvrage. On va naturellement laisser le premier bouquin ouvert et prendre dans la bibliothèque un bouquin identique, et ainsi de suite.
On aura donc sur la table autant de livres identiques ouverts à des pages différentes ou identiques. On peut même empiler les livres ouverts à la page concernée, d'où le nom de pile (LastInFirstOut) Quand on aura trouvé la réponse sur le énième bouquin, on pourra le fermer et le ranger, puis continuer la lecture de l'article sur le précédent, puis le refermer, etc. jusqu'à revenir sur le premier, terminer l'article et enfin le refermer.
Avec une méthode itérative, c'est toujours le même bouquin qui est consulté, mais l'article lu ne renvoie pas à un autre article. On n'a besoin que d'une toute petite table.
Skullkid a écrit:L'analogie de Dlzlogic avec les livres correspond à de la récursivité dite "non terminale", qui en effet requiert par défaut beaucoup plus d'espace mémoire qu'une méthode itérative. Mais il y a aussi la récursivité terminale, qui ne prend pas plus de mémoire qu'une méthode itérative. L'idée est de faire en sorte que les appels récursifs soient exécutés en dernier à chaque niveau de récursion, de sorte qu'il n'y a pas à remonter la descente récursive. En gros, si l'article 2 du journal A renvoie à l'article 15 du journal B, on n'a pas besoin de garder le journal A sur la table puisqu'on sait qu'on n'en aura plus besoin.
Tout algorithme peut s'écrire itérativement ou récursivement, les deux ont leurs avantages et les compilateurs d'aujourd'hui sont très doués pour optimiser les empreintes mémoire des algorithmes récursifs. Certaines structures de données (les octrees, par exemple) et méthodes de programmation (divide and conquer, par exemple) très efficaces sont intimement liées à la récursivité.
Au final c'est surtout une question de goût. À une époque il y avait de vraies raisons de préférer l'itératif (les compilateurs n'étaient pas adaptés, l'espace mémoire était une denrée rare, ...) mais la plupart sont devenues obsolètes et les points forts du récursif (algorithmes de présentation claire, structures de données adaptées) font qu'il est souvent préféré dans beaucoup de problèmes. Bien sûr il faut l'utiliser intelligemment (tout comme l'itératif d'ailleurs), mais je ne vois pas pourquoi Dlzlogic conseille de limiter son usage au maximum.
bifur := proc (rmin, rmax, n, u0, e, p, m)
local un, etapun, f, k, L, r;
L := [];
un := proc (r, n)
local u, i, f;
f :=x-> x*r*(1-x);
u := u0;
for i to n do u := f(u) end do;
u ;
end proc;
for r from rmin by p to rmax do
k := 2;
if abs(un(r, n)-un(r, n+1)) < e then L := [op(L), [r, un(r, n)]]
else
L := [op(L), [r, un(r, n)], [r, un(r, n+1)]];
while e < abs(un(r, n)-un(r, n+k)) and k < m do
k := k+1;
L := [op(L), [r, un(r, n+k)]] end do
end if
end do;
plots:-pointplot(L, style = point, symbol = point, trickness = 0)
end proc
Dlzlogic a écrit:En fait, ma question est simple, s'agit-il d'une particularité de certains langages (type Camel), ou est-ce un méthodee applicable à tous les langages, par exemple C ?
factorielle(n)
si n = 0
alors 1
sinon n*factorielle(n-1)
fin si
fin
factorielle_aux(n,acc)
si n = 0
alors acc
sinon factorielle_aux(n-1,n*acc)
fin si
fin
factorielle(n)
factorielle_aux(n,1)
fin
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 31 invités
Tu pars déja ?
Identification
Pas encore inscrit ?
Ou identifiez-vous :