9 avril 2019

Algorithme de parcours en profondeur

L'algorithme de parcours en profondeur correspond à la méthode intuitive qu'on utilise pour trouver la sortie d'un labyrinthe. En effet, il suffit de toujours longer le mur pour trouver la sortie. (labyrinthe parfait)
1️⃣️
On indique que le nœud a été exploré.
2️⃣️
On arrête si nous sommes sur le nœud recherché. (non obligatoire)
3️⃣️
On répète la procédure par récursivité pour tous les enfants du nœud non explorés.


Un algorithme qui contient un ou des appels à lui-même est dit récursif. Ce procédé est souvent employé dans la conception d'algorithmes basée sur le paradigme diviser pour régner.

Voici un exemple de récursivité avec une fonction de puissance. 
int Power(int value, int p)
{
  return p != 0
    ? value * Power(value, --p)
    : 1;
}

Attention à ne pas dépasser la taille de la pile des exécutions (Sauvegarde des appels de fonctions). En électronique embarquée, la récursivité est souvent proscrite ! L'utilisation de la pile restant trop imprévisible.
Labels: