On se rend vite compte qu'en fait, on peut la coder
fact(n)=
res=1
for i=1 to n: res=res*i
return(res)
L'avantage de la première version, c'est que c'est plus proche de la définition mathématique. L'inconvéniant, c'est le nombre d'appel récursif qui peut exploser la pile. L'avantage de la second, c'est la pile. L'inconvéniant, c'est que c'est moins proche de la fonction mathématique.
En fait, de façon générale, on peut toujours transformer un code recursif en un code impératif. Il suffit de manipuler une pile et de faire un while qui englobe le tout. Fait sous cette forme, ce n'est pas intéressant. En revanche, certain type de récursion (les récursion terminales) peuvent se coder avec une bête boucle for. De plus, cette procédure de dé-recursifier s'automatise. Certains langages le détectent et optimisent tout seuls.
[^] # Re: sonntag
Posté par fmaz fmaz . En réponse à la dépêche Lisaac 0.12 en GPL v3. Évalué à 1.
Si tu codes la factorielle par
fact(n)=
si n=0 then 1
else n*fact(n-1)
On se rend vite compte qu'en fait, on peut la coder
fact(n)=
res=1
for i=1 to n: res=res*i
return(res)
L'avantage de la première version, c'est que c'est plus proche de la définition mathématique. L'inconvéniant, c'est le nombre d'appel récursif qui peut exploser la pile. L'avantage de la second, c'est la pile. L'inconvéniant, c'est que c'est moins proche de la fonction mathématique.
En fait, de façon générale, on peut toujours transformer un code recursif en un code impératif. Il suffit de manipuler une pile et de faire un while qui englobe le tout. Fait sous cette forme, ce n'est pas intéressant. En revanche, certain type de récursion (les récursion terminales) peuvent se coder avec une bête boucle for. De plus, cette procédure de dé-recursifier s'automatise. Certains langages le détectent et optimisent tout seuls.