Ressource pédagogique : 4.9. Recursion can be avoided: an iterative version
Présentation de: 4.9. Recursion can be avoided: an iterative version
Informations pratiques sur cette ressource
Droits réservés à l'éditeur et aux auteurs. 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.
Description de la ressource pédagogique
Description (résumé)
We have written a recursive function to compute the optimal path that is an optimal alignment between two sequences. Here all the examples I gave were onDNA sequences, four letter alphabet. OK. The writing of this recursive function is very elegant but unfortunately we will see now that it isnot very efficient in execution time. Let's see why. Remember the computing schema weapply during the recursion, for example here, to compute the cost of this node, we saw that it was required to computerecursively the cost of that node, that node and that node. OK but to compute the cost of that node here, you need to compute the cost of that one, that oneand that one again that is this cost which was computed in order to compute the code of the ending node here has to be recomputed in the recursive function to compute the cost of that node. In a more general way, to computethe cost of a node like this one, you need to compute all of these nodes here but to compute the cost of that node, you need to compute all the costs of these nodes again and again and again. So the cost of one node in thiswriting of the function is computed many, many, many times. It's because we use this recursive function so it was nice but it was expensive in terms of execution time. So we can imagine a new version of the algorithm which is not recursive but iterative in two phases. Let's see how it works.
"Domaine(s)" et indice(s) Dewey
- biologie application informatique (570.285)
Thème(s)
Document(s) annexe(s) - 4.9. Recursion can be avoided: an iterative version
- Cette ressource fait partie de
AUTEUR(S)
-
Francois RECHENMANN
EN SAVOIR PLUS
-
Identifiant de la fiche
35255 -
Identifiant
oai:canal-u.fr:35255 -
Schéma de la métadonnée
- LOMv1.0
- LOMFRv1.0
- Voir la fiche XML
-
Entrepôt d'origine