Discussion :

[Devilju69]

Bonjour je comprend pas comment peut-on parcourir une listes chainées de manière itérative ? Et quelle est la différences avec la manière récursive ?
Merci d'avance

[souviron34]

Code :

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

1
2
3
4
5
6
element = premier
Tant que element non NULL
    on fait quelque chose
    ...
    element = element -> suivant 
Fin tant que

[Sve@r]

Et quelle est la différences avec la manière récursive ?

Un algo récursif s'appelle lui-même alors qu'un algo itératif, comme le montre Souviron, consiste en une boucle faisant varier un repère.

Voici l'exemple de Souviron écrit en récursif

Code :

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

1
2
3
4
5
6
7
FONCTION(element)
DEBUT
    on fait quelque chose
    SI element->suivant non NULL
        FONCTION(element->suivant)
    FIN SI
FIN

[Trap D]

Mouaih, moi je ferais plutôt :

Code :

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

1
2
3
4
5
6
7
FONCTION(element)
DEBUT
    SI element non NULL ALORS
        on fait quelque chose
        FONCTION(element->suivant)
    FIN SI
FIN

Ça permet de ne pas planter si on appelle la fonction avec NULL
A noter que comme la récursion est terminale, il y a de fortes chances pour que le compilo transforme ça en tant que.

[Sve@r]

Mouaih, moi je ferais plutôt :

Code :

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

1
2
3
4
5
6
7
FONCTION(element)
DEBUT
    SI element non NULL ALORS
        on fait quelque chose
        FONCTION(element->suivant)
    FIN SI
FIN

Ça permet de ne pas planter si on appelle la fonction avec NULL

C'était effectivement comme ça que je l'avais écrit initialement. Le problème de ce genre de code est que, pour éviter un test initial que tu ne feras qu'une fois (à savoir vérifier que t'appelles pas la fonction avec un élément nul) tu génères un appel récursif supplémentaire (avec toutes les contraintes qui y sont liées comme la sauvegarde du contexte, etc) et inutile (puisque t'appelles la fonction pour le NUL de la fin de liste).

A noter que comme la récursion est terminale, il y a de fortes chances pour que le compilo transforme ça en tant que.

Dans ce cas précis oui. Mais on parle de cas plus généraux dans lesquels la récursivité terminale n'a pas lieu d'être...

[Emmanuel Delahaye]

Bonjour je comprend pas comment peut-on parcourir une listes chainées de manière itérative ?

http://emmanuel-delahaye.developpez....s_chainees.htm

Et quelle est la différences avec la manière récursive ?

C'est plus sûr si il y a des risques de débordement de pile avec la récursivité (trop grande profondeur).