# Portabilitaet: UNIVERSAL
# Zuletzt validiert: 2026-01-28 (Gemini)
# Naechste Pruefung: 2027-01-28
# Quellen: [informatik/algorithmen/README.txt]

REKURSION
=========

Stand: 2026-01-28

WAS IST REKURSION?
------------------
Rekursion ist ein Programmierkonzept, bei dem eine Funktion sich selbst aufruft, um ein Problem in kleinere Teilprobleme zu zerlegen.
Es folgt dem Prinzip: "Um das Grosse zu loesen, loese das Kleine."

AUFBAU EINER REKURSIVEN FUNKTION
--------------------------------
Jede rekursive Funktion braucht zwingend zwei Teile, sonst entsteht eine Endlosschleife (Stack Overflow):

1. **Basisfall (Base Case):** Die Abbruchbedingung. Das kleinste Problem, das trivial lösbar ist.
2. **Rekursionsschritt:** Der Selbstaufruf mit einem "kleineren" Argument, das Richtung Basisfall fuehrt.

BEISPIEL: FAKULTAET (5!)
------------------------
Mathematik: 5! = 5 * 4 * 3 * 2 * 1

```python
def factorial(n):
    # 1. Basisfall
    if n <= 1:
        return 1
    
    # 2. Rekursionsschritt
    return n * factorial(n - 1)
```

WIE ES FUNKTIONIERT (CALL STACK)
--------------------------------
Jeder Funktionsaufruf landet auf dem "Call Stack" (Stapel).
1. `factorial(3)` ruft `factorial(2)`
2. `factorial(2)` ruft `factorial(1)`
3. `factorial(1)` returniert 1 (Basisfall!)
4. `factorial(2)` nimmt die 1, rechnet 2*1 = 2, returniert 2.
5. `factorial(3)` nimmt die 2, rechnet 3*2 = 6, returniert 6.

VOR- UND NACHTEILE
------------------
**Vorteile:**
- Eleganter, lesbarer Code fuer hierarchische Strukturen (Baeume, Dateisysteme).
- Natuerliche Loesung fuer Divide & Conquer (Merge Sort).

**Nachteile:**
- Speicherverbrauch (Stack). Bei zu tiefer Rekursion droht `RecursionError`.
- Oft langsamer als iterative Loesungen (Schleifen) durch Overhead der Funktionsaufrufe.

TAIL RECURSION (ENDREKURSION)
-----------------------------
Spezialform, bei der der rekursive Aufruf die allerletzte Aktion ist. Manche Compiler koennen das zu einer Schleife optimieren (Python tut dies NICHT automatisch).

TYPISCHE ANWENDUNGEN
--------------------
- Baum-Traversierung (DOM, AST, Verzeichnisse).
- Graphen-Suche (DFS).
- Fraktale.
- Tueftel-Spiele (Tuerme von Hanoi).

SIEHE AUCH
----------
wiki/informatik/algorithmen/komplexitaet.txt
wiki/informatik/datenstrukturen/baeume.txt
