Vidéo pédagogique
Notice
Sous-titrage
Sous-titre
Langue :
Français
Crédits
François Rechenmann (Intervention), Thierry Parmentelat (Intervention)
Conditions d'utilisation
Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.
DOI : 10.60527/nxzw-n353
Citer cette ressource :
François Rechenmann, Thierry Parmentelat. Inria. (2015, 1 juin). 4.9. Éviter la récursivité : une version itérative , in 4. Comparaison de séquences. [Vidéo]. Canal-U. https://doi.org/10.60527/nxzw-n353. (Consultée le 9 juillet 2025)
logo Inria
Inria - Institut national de recherche en sciences et technologies du numérique
S'abonner
Contacter

4.9. Éviter la récursivité : une version itérative

Réalisation : 1 juin 2015 - Mise en ligne : 4 octobre 2016
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

La fonction récursive que nous avons obtenue est d'un code assez compact et plutôt élégant, mais effectivement peu efficace. Pourquoi ? Rappelons son fonctionnement. Cette fonction est d'abord appelée pour calculer le coût de ce nœud-là. Nécessitant le coût optimal de ce nœud, celui-ci et celui-là, elle est ré appliquée, elle se ré appelle sur ces 3 nœuds-là. Si on prend l'appel de la fonction sur ce nœud-là, elle va se ré appeler de nouveau pour calculer le coût de ce nœud, de celui-ci et de celui-là. Conséquence : vous voyez que ce nœud-là a déjà été calculé 2 fois : une première fois ici et une deuxième fois là. Or, ce nœud-là pour se calculer va utiliser tous ces nœuds-là. De la même manière qu'ici un même nœud est calculé plusieurs fois, à l'intérieur ici tous ces nœuds-là vont aussi être calculés plusieurs fois. C'est véritablement une catastrophe du point de vue efficacité. Joli code, très mauvaise efficacité.
Est-ce qu'on peut faire mieux ? Oui, on va faire mieux en imaginant un algorithme itératif, non plus récursif, qui va travailler en 2 phases. Dans la première phase, on va calculer le coût du chemin optimal qui va du nœud 00 et qui aboutit à chaque nœud IJ, chaque nœud IJ de notre grille. Et on va enregistrer ces coûts dans un tableau de dimension 0N-0M.
Comment va-t-on calculer ces coûts ? En fait, c'est assez simple, on part encore une fois du nœud 00, le coût est connu : 0. Le coût de ce nœud-là et de celui-ci, on l'a vu tout à l'heure, est connu, c'est un coût d'insertion : Bêta. Ici, 2 Bêta. Mais déjà à partir du moment où on a le coût ici celui-ci et celui-là, on sait par notre schéma de calcul étudié précédemment comment calculer le coût de ce nœud-là. Possédant le coût de ce nœud-là, celui-là étant connu, on peut calculer celui-là, celui-là, celui-là, celui-là et ainsi de suite. Et on peut donc calculer le coût de ce nœud-là et tous ceux de sa diagonale telle qu'on peut le voir ici...

Intervention
Thème
Disciplines :
Documentation
Support de présentation au format PDF

Dans la même collection

Voir tout

Avec les mêmes intervenants et intervenantes

Sur le même thème