Wie funktioniert Rekursion?
Wenn eine Fuktion/Methode als rekursiv bezeichnet wird, bedeutet es, dass sie sich selbst erneut aufruft. Hier ist ein Beispiel für eine rekursive Funktion:public int berechneFakultaet(int n) {
if (n == 0 || n == 1) {
return 1;
}
return n * berechneFakultaet(n - 1);
}Beispielaufruf mit :
- Erster Aufruf
- Da nicht gleich oder ist, wird der rekursive Fall aufgerufen
- Die Methode ruft sich selbst mit also auf
- Zweiter Aufruf
- Da nicht gleich oder ist, wird der rekursive Fall aufgerufen
- Die Methode ruft sich selbst mit also auf
- Dritter Aufruf
- Da gleich ist, wird zurückgegeben
- Fortsetzung des zweiten Aufrufs
- Da ist, wird zurückgegeben
- Fortsetzung der ersten Aufrufs
- Da ist, wird zurückgegeben
Zusammenfassung des Aufrufs:
berechneFakultaet(3)
-> berechneFakultaet(2)
-> berechneFakultaet(1) --> Rückgabe: 1
-> 2 * 1 = 2 --> Rückgabe: 2
-> 3 * 2 = 6 --> Rückgabe: 6
„Teile und Herrsche“ ist eine leistungsstarke Methode beim Entwurf rekursiver Algorithmen. Sie zerlegt ein Problem in kleinere Teilprobleme, löst diese rekursiv und kombiniert die Teillösungen, um das Gesamtproblem zu lösen. Die Strategie führt oft zu effizienten und eleganten Lösungen, insbesondere bei Problemen wie Sortieren, Suchen und vielen anderen, bei denen sich das Problem in Teilprobleme zerlegen lässt.
Beispiel: Merge-Sort