algorithme

Récursion, Pile, File et Recherche en Profondeur (DFS)

En programmation, la récursion et les structures de données comme la pile (Stack) et la file (Queue) sont des concepts essentiels. Ces notions sont largement utilisées, notamment dans la recherche en profondeur (DFS). Cet article couvre :

• Le fonctionnement de la récursion
• Les piles et leurs opérations
• Les files et leur différence avec les piles
• Comment DFS exploite la récursion

---

1. Récursion : un concept fondamental

Qu'est-ce que la récursion ?

La récursion est une technique où une fonction s'appelle elle-même pour résoudre un sous-problème plus petit du problème initial. Une fonction récursive comporte :

• Un cas de base – condition d'arrêt.
• Un cas récursif – appel à la fonction avec un paramètre réduit.

Exemple : Calcul de la factorielle

La factorielle de n est définie comme :

n! = n × (n-1) × (n-2) × ... × 1

Implémentation récursive en C++ :

int fact(int n) {

    if (n == 0) return 1; 

    return n * fact(n - 1);

}

2. La Pile (Stack) : structure LIFO

Qu'est-ce qu'une pile ?

Une pile est une structure de données qui suit le principe LIFO (Last In, First Out), ce qui signifie que le dernier élément ajouté est retiré en premier.

Opérations principales :

• push(x) : ajoute un élément.
• pop() : retire l'élément du sommet.
• top() : renvoie l'élément au sommet.

Exemple en C++ :

#include <stack>

#include <iostream>

using namespace std;

int main() {

    stack<int> s;  

    s.push(1);   

    s.push(2);   

    s.push(3);   

    cout << s.top() << endl; // 3

    s.pop();  

    cout << s.top() << endl; // 2

    return 0;

}

---

3. La File (Queue) : structure FIFO

Qu'est-ce qu'une file ?

Une file est une structure de données qui suit le principe FIFO (First In, First Out), ce qui signifie que le premier élément ajouté est retiré en premier.

Opérations principales :

• push(x) : ajoute un élément à la fin.
• pop() : retire le premier élément.
• front() : renvoie le premier élément.

Exemple en C++ :

#include <queue>

#include <iostream>

using namespace std;

int main() {

    queue<int> q;

    q.push(1);

    q.push(2);

    q.push(3);

    cout << q.front() << endl; // 1

    q.pop();  

    cout << q.front() << endl; // 2

    return 0;

}

Comparaison entre Pile et File

Caractéristique	Pile (LIFO)	File (FIFO)
Ajout	push(x) au sommet	push(x) à la fin
Suppression	pop() retire le sommet	pop() retire le premier élément
Ordre	Dernier arrivé, premier sorti	Premier arrivé, premier sorti

---

4. Recherche en Profondeur (DFS)

Qu'est-ce que DFS ?

La recherche en profondeur (DFS) est un algorithme de parcours des graphes qui explore chaque branche au maximum avant de revenir en arrière.

Exemple d'arbre traversé en DFS :

        1

       / \

      2   7

     / \   \

    3   6   11

   / \   \

  4   5   8

         / \

        9   10

Implémentation de DFS en C++ :

void dfs(int node) {

    visited[node] = true;

    for (int neighbor : adj[node]) {

        if (!visited[neighbor]) {

            dfs(neighbor);

        }

    }

}

---

Conclusion

• La récursion facilite la résolution des problèmes en les décomposant.
• La pile suit le principe LIFO et est souvent utilisée en récursion.
• La file suit le principe FIFO et est souvent utilisée en BFS.
• DFS utilise la pile et est un puissant algorithme de parcours.

Ces concepts sont essentiels en algorithmique et structures de données. Essayez de les coder pour mieux les comprendre !