Rekursion in C

Rekursion ist eine Technik, bei der eine Funktion sich selbst aufruft, um ein Problem zu lösen.

In dieser Lektion lernen Sie:

• Was Rekursion ist und wie sie funktioniert.
• Wie Sie rekursive Funktionen implementieren.
• Den Unterschied zwischen Rekursion und Iteration.

Was ist Rekursion?

Bei Rekursion ruft eine Funktion sich selbst auf, um einen kleineren Teil eines Problems zu lösen.

Beispielsyntax:

void function() { function(); // Recursive call }

Jede rekursive Funktion muss einen Basisfall enthalten, um eine Endlosrekursion zu verhindern.

Beispiel: Rekursion

Dieses Programm veranschaulicht Rekursion, indem es die Zahlen von 5 bis 1 ausgibt.

#include <stdio.h>

void countDown(int n) {
    if (n <= 0) return; // Base case
    printf("%d\n", n);
    countDown(n - 1); // Recursive call
}

int main() {
    countDown(5);
    return 0;
}

Basisfall bei der Rekursion

Eine rekursive Funktion muss einen Basisfall enthalten, um die Rekursion zu beenden.

Beispiel:

if (n == 0) return;

Ohne einen Basisfall würde die Funktion sich unendlich oft selbst aufrufen, was zu einem Stapelüberlauf führt.

Beispiel: Fakultät mithilfe von Rekursion

Dieses Programm berechnet die Fakultät einer Zahl mithilfe von Rekursion.

#include <stdio.h>

int factorial(int n) {
    if (n == 0) return 1; // Base case
    return n * factorial(n - 1);
}

int main() {
    printf("Factorial of 5: %d\n", factorial(5));
    return 0;
}

Rekursion vs. Iteration

Mit Rekursion und Iteration (Schleifen) lassen sich dieselben Ergebnisse erzielen, aber sie funktionieren unterschiedlich.

Unterschiede:

• Rekursion verwendet Funktionsaufrufe und benötigt mehr Speicher.
• Iteration verwendet Schleifen und ist im Allgemeinen effizienter.
• Rekursion macht den Code bei Problemen wie Baumdurchläufen einfacher.

Beispiel: Fibonacci-Folge (rekursiv)

Dieses Programm berechnet die Fibonacci-Folge mithilfe von Rekursion.

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    printf("Fibonacci(5): %d\n", fibonacci(5));
    return 0;
}

Wann sollten Sie Rekursion verwenden?

Rekursion eignet sich für Probleme, die Folgendes umfassen:

• Das Durchlaufen von Bäumen.
• Backtracking (z. B. zum Lösen von Labyrinthen).
• Mathematische Probleme wie Fakultät und Fibonacci-Folgen.

Zusammenfassung

In dieser Lektion haben Sie Folgendes gelernt:

• Was Rekursion ist und wie sie funktioniert.
• Wie wichtig ein Basisfall ist.
• Der Unterschied zwischen Rekursion und Iteration.

Als Nächstes sehen Sie sich Arrays und Zeichenketten in C an!