Algorithmus

Rekursion, Stack, Queue und Tiefensuche (DFS)

In der Informatik sind Rekursion und Datenstrukturen wie Stacks und Queues grundlegende Konzepte. Sie werden häufig in Algorithmen wie der Tiefensuche (DFS) verwendet. In diesem Artikel behandeln wir:

• Das Konzept der Rekursion
• Stacks und ihre Operationen
• Queues und ihre Unterschiede zu Stacks
• Wie DFS auf Rekursion basiert

---

1. Rekursion: Ein grundlegendes Konzept

Was ist Rekursion?

Rekursion bedeutet, dass eine Funktion sich selbst aufruft, um ein kleineres Teilproblem zu lösen. Eine rekursive Funktion besteht aus:

• Basisfall – Stoppt die Rekursion.
• Rekursiver Fall – Die Funktion ruft sich selbst auf.

Beispiel: Fakultät berechnen

Die Fakultät von n wird definiert als:

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

Rekursive Implementierung in C++:

int fakultaet(int n) {

    if (n == 0) return 1; 

    return n * fakultaet(n - 1);

}

2. Der Stack: LIFO-Datenstruktur

Was ist ein Stack?

Ein Stack ist eine Datenstruktur, die nach dem LIFO-Prinzip (Last In, First Out) arbeitet. Das bedeutet, dass das zuletzt hinzugefügte Element zuerst entfernt wird.

Grundlegende Operationen:

• push(x) – Fügt ein Element hinzu.
• pop() – Entfernt das oberste Element.
• top() – Gibt das oberste Element zurück.

Beispiel in 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. Die Queue: FIFO-Datenstruktur

Was ist eine Queue?

Eine Queue ist eine Datenstruktur, die nach dem FIFO-Prinzip (First In, First Out) arbeitet. Das bedeutet, dass das zuerst hinzugefügte Element auch als erstes entfernt wird.

Grundlegende Operationen:

• push(x) – Fügt ein Element am Ende hinzu.
• pop() – Entfernt das erste Element.
• front() – Gibt das erste Element zurück.

Beispiel in 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;

}

Vergleich: Stack vs. Queue

Eigenschaft	Stack (LIFO)	Queue (FIFO)
Hinzufügen	push(x) oben	push(x) am Ende
Entfernen	pop() entfernt das oberste Element	pop() entfernt das erste Element
Reihenfolge	Zuletzt rein, zuerst raus	Zuerst rein, zuerst raus

---

4. Tiefensuche (DFS)

Was ist DFS?

Die Tiefensuche (Depth-First Search, DFS) ist ein Algorithmus zur Traversierung von Graphen, bei dem jeder Zweig maximal erkundet wird, bevor zurückgegangen wird.

Beispiel für einen DFS-Durchlauf:

        1

       / \

      2   7

     / \   \

    3   6   11

   / \   \

  4   5   8

         / \

        9   10

DFS-Implementierung in C++:

void dfs(int node) {

    visited[node] = true;

    for (int neighbor : adj[node]) {

        if (!visited[neighbor]) {

            dfs(neighbor);

        }

    }

}

---

Fazit

• Rekursion hilft bei der Lösung komplexer Probleme.
• Der Stack folgt dem LIFO-Prinzip und wird oft in Rekursionen verwendet.
• Die Queue folgt dem FIFO-Prinzip und wird oft in BFS verwendet.
• DFS nutzt den Stack und ist ein wichtiger Suchalgorithmus.

Diese Konzepte sind grundlegend für Algorithmen und Datenstrukturen. Versuche, sie selbst zu implementieren!