Ressource pédagogique : 4.8. A recursive algorithm

Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

We have seen how we can computethe optimal cost, the ending node of our grid if we know the optimal cost of the three adjacent nodes. This is this computation scheme we can see here using the notation of the pseudo code and not the mathematical notation we used in the previous sessions. So again we can compute the cost of this node if we know the cost of that node, that node and that node and we have to add respectively the insertion cost, the substitution cost orthe insertion cost. The substitution cost here depends on the letter at this position in the sequence and this letter atthe position of the first sequence. The interesting point here is tounderstand that this scheme can also be applied for that node. If you make the hypothesis, you know the costs at that node, at that node and that node, then using the same schema you can compute the cost at that node. The same cost which will be used to compute the cost at the ending node. So this is the scheme at the basis of our recursive function. What is a recursive function? A recursive function is something which may appear a bit magic the first time because it's a function which is called within its own execution. You call the function, it begins the execution and at one or several points the function is called again, that's why it's called recursive.

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

• biologie application informatique (570.285)

Thème(s)