Discussion :

[Jedai]

par exemple il existe une solution itérative aux tours de Hawaï

Ca ne serait pas les tours de Hanoï ?

...

[Trap D]

Et pourquoi il n'y aurait pas des tours à Hawaï

[Jean-Marc.Bourguet]

Oui, on peut calculer la complexité d'une fonction récursive (enfin, de certaines d'entre elles). Non les fonctions récursives ne sont pas toujours linéarisables.

heu, je ne suis pas renseigné, mais mon professeur de maths m'a dis qu'il existais une démonstration prouvant que TOUTES les fonctions récursives étaient linéarisable.
il m'a même affirmé qu'il existais de "linéariseurs" de fonctions.

Qu'entends-tu par linéarisable? Oui, il est possible de faire une version non récursive de toute fonction récursive, mais
* pour ce faire on a besoin pour certaines d'entre elles d'utiliser une pile
* on n'arrive pas pour autant à un comportement linéaire.

[Jean-Marc.Bourguet]

pour moi, la linéarisation d'une fonction récursive consiste en sa transformation en une fonction ne contenant que des boucles et des instructions successives et ayant un nombre limité et prédéfini de variable.

Variable est un peu trop vague; tellement vague que je peux prétendre programmer n'importe quel algo en n'ayant besoin que d'une seule variable d'un type convenablement choisi :-)

Essaie de faire une implémentation non récursive du quick sort sans avoir besoin d'une quantité de mémoire proportionnelle à la profondeur d'appel maximale de la version récursive.

[Jean-Marc.Bourguet]

Un bon exo est de dérécursiver la fonction d'Ackermann :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
La fonction d'Ackermann est la fonction définie sur les couples d'entiers naturels par les formules de récurrence suivante : 
A(0,n)=n+1 
A(m,0)=A(m-1,1) 
A(m,n)=A(m-1,A(m,n-1)) 
  La fonction d'Ackermann est très compliquée à calculer, car très récursive. Son calcul sur un ordinateur conduit souvent au débordement de la pile!

Il em semble qu'on en a déjà parlé ici.

Ça m'intéresse. Aurais-tu un pointeur? La fonction rechercher m'indique qu'il y a des messages mais ils n'ont plus l'air accessible et je n'arrive pas à les retrouver dans le cache de google.

[Trap D]

Je pense qu'il faudrait demander au modérateur du forum de les ressortir. Il me semble que quelqu'un était "presque" arrivé à une solution, mais je n'en suis pas sûr.

[méphistopheles]

pour moi, la linéarisation d'une fonction récursive consiste en sa transformation en une fonction ne contenant que des boucles et des instructions successives et ayant un nombre limité et prédéfini de variable.

Variable est un peu trop vague; tellement vague que je peux prétendre programmer n'importe quel algo en n'ayant besoin que d'une seule variable d'un type convenablement choisi :-)

Essaie de faire une implémentation non récursive du quick sort sans avoir besoin d'une quantité de mémoire proportionnelle à la profondeur d'appel maximale de la version récursive.

disons pour préciser, des variables du même type que celles utilisées dans la procédure récursive: si je n'ai une variable d'appel "entiére" dans ma récursive, je dois n'avoire que des variables de type entier, et non pas des listes d'entiers où autres tableus permettants de stocker à peu-pres n'importe quoi.
en prenant un exemple simple et concret:
une fonction du calcul du cosinus consiste à faire une fonction récursive du type:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
fonction cos(variable: n)
si n< précision alors renvoyer n sinon, renvoyer 2(cos (n/2))^2 -1

cette fonction peut se linéariser de la ma,ière suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
fonction cos(variable: n)
a:=0
tant que n>précision
n:=n/2
a:=a+1
boucler.
pour n depuis 0 jusqu'a a :
n:=2n^2-1
boucler
renvoyer n

ici, elle est évidente mais dans d'autres cas, on est tenté de stocker des valeurs dans un tableau pui de les resortirs en "remontant " la récursiviter, ce qui consiste à faire une "pile manuelle".


salut

[Jean-Marc.Bourguet]

ici, elle est évidente mais dans d'autres cas, on est tenté de stocker des valeurs dans un tableau pui de les resortirs en "remontant " la récursiviter, ce qui consiste à faire une "pile manuelle".

Je n'ai aucun problème à transformer une récursivité terminale en itération; je peux même le faire pour les récursivités non terminales ayant besoin d'une variable d'accumulation (cas typique, la factorielle exprimée de manière récusive) ou d'autres cas particuliers. J'ai pratiqué assez les langages fonctionnels pour savoir que les compilateurs pour ces langages sont même capables de faire certaines de ces transformations tout seul et je m'y connais assez en compilation pour avoir une assez bonne idée comment faire un tel compilateur.

Mais ces méthodes ne sont pas générales (en particulier je ne vois pas de méthodes applicables quand il y a plusieurs appels récursifs même si certains cas sont faisables) et j'ai dans mes cartons un certain nombre d'algos (je t'en ai donné un comme défi, je peux t'en sortir d'autres, en particulier sur les graphes mais si tu résous ce défi je pense être capable de faire la transformation moi-même) pour lesquels je doute qu'il y ait une implémentation itérative n'ayant pas besoin d'espace auxilliaire proportionnel à la profondeur d'appel maximale de la version récursive.

Ce genre de recherche n'est pas particulièrement dans mon domaine, mais le résultat que tu prétends exister me surprend tellement que j'aimerais une référence.

[Sib]

Edit : Autant retirer cette partie, je n'y avait raconté que des conneries ^^'..

Je suis peut-être à coté de la plaque mais par simple curiosité, y-ast'il une complexité associée aux fonctions récursives (qui sont toujours linéarisables) et si oui, laquelle.

Pour la complexité des algorithmes récursifs de type "Diviser pour Régner", on peut utiliser le Théorème Maître (Master Theorem) :
T(n) = a * T(n/b) + f(n)
où :
- T(n) est la complexité de l'algorithme récursif
- a le nombre de sous-problèmes et n/b la taille de chacun de ces sous-problèmes lors de l'étape appelée "Régner"
- f(n) la complexité des étapes "Diviser" et "Combiner" (hors appels récursifs)

[Jedai]

Pour en revenir aux complexités, il ne faut pas toujours utiliser la notation grand O car c'est un majorant et ne montre pas forcément l'allure d'une fonction. (une fonction en O(n) est aussi une fonction en O(n^2)). Il vaut mieux utiliser la fonction sigma qui là nous donne plus d'information sur le comportement des fonctions.

La notation grand O permet de connaître le comportement d'un algorithme, indépendamment des paramètres relatifs à son implémentation, tels que la puissance de la machine, le langage utilisé, l'optimisation du code,..
Un algorithme en O(n) n'est pas un algorithme en O(n^2) !

Bien sûr que si !
f(n) = O(g(n)) signifie :
Il existe N tq Pour tout n > N, Il existe A > 0 tq f(n) <= A * g(n)

Donc tout algorithme en O(n) est aussi en O(n^2) !!

--
Jedaï

[Sib]

Bien sûr que si !
f(n) = O(g(n)) signifie :
Il existe N tq Pour tout n > N, Il existe A > 0 tq f(n) <= A * g(n)

Donc tout algorithme en O(n) est aussi en O(n^2) !!

Ouhla.. Aux temps pour moi....

Ya vraiment des jours où je ferais mieux de.... me taire..


/me slaps himself..