« Programmation algorithmique/Listes simplement chaînées » : différence entre les versions

== Itération contre récursion ==

 

La récursion (ou récursivité) se rattache plus à l'algorithmique fonctionnelle qu'à l'algorithmique impérative.

Toutefois, les langages impératifs offrent souvent la possibilité de programmer par récursion, alors il est intéressant de choisir entre itération et récursion en toute connaissance de cause.

 

Selon le langage et le compilateur utilisé pour réaliser cet algorithme, les appels récursifs successifs seront stockés ou non en mémoire. On parle de pile d'appels récursifs. Dans le cas où le support d'exécution (c'est à dire l'interprète ou le code compilé) utilise une pile d'appels récursifs pour exécuter la fonction RECH_REC, la complexité en espace sera O(N), car pour chaque élément de la liste, on devra stocker en mémoire, sur la pile, l'information sur l'appel en cours. Dans le second cas, où le compilateur est capable de générer du code qui utilise un espace limité sur la pile, la complexité en espace sera O(1), comme pour la version itérative.

 

== Insertion ==