Ressource pédagogique : 4.8. Un algorithme récursif

Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

Nous avons désormais en main tous les éléments pour écrire notre algorithme de détermination d'un alignement optimal, ici d'un chemin optimal. Avec les notations que nous avons introduites, je vous rappelle que nous savons, à priori, déterminer le coût de ce noeud-là, autrement dit le coût du chemin aboutissant sur ce noeud, en faisant l'hypothèse que nous connaissons les coûts optimaux de ces trois noeuds-là. Avant de poursuivre, il convient de comprendre que ce schéma de calcul, qu'on utilise pour calculer le coût de ce noeud-là, est aussi utilisable pour calculer le coût de ce noeud-là, à partir des coûts de ce noeud et de ce noeud-là, à travers un des trois chemins possibles. De même, le coup de ce noeud-là peut être calculé avec le même schéma de calcul à partir du coût de ce noeud-là, celui-ci et celui-là, et ainsi de suite. Et ainsi de suite, en remontant jusqu'au noeud 00. Ceci nous donne un schéma de calcul récursif que nous allons implémenter dans une fonction récursive. Qu'est-ce qu'une fonction récursive ? Une fonction récursive est une fonction qui fait appel à elle-même, qui s'appelle elle-même, au cours même de son exécution. Elle s'exécute, et au cours de son exécution, elle s'appelle elle-même. Et donc, on va avoir une cascade d'appels. Elle est en train de s'exécuter, elle s'appelle, elle s'exécute, elle s'appelle et cetera...

"Domaine(s)" et indice(s) Dewey

• biologie application informatique (570.285)

Thème(s)