Rekursive bzw. induktive Definition

Eine Funktion $f$ über $\mathbb{N}$ kann rekursiv bzw. induktiv definiert werden, indem:

• die ersten Funktionswerte explizit angegeben werden und
• spätere Werte mit Hilfe vorheriger Werte definiert werden.

Explizite Form

Sei $f:\mathbb{N}\to \mathbb{N}$ rekursiv definiert.

Eine explizit definierte Funktion $g:\mathbb{N}\to \mathbb{N}$ mit

für alle $n\in \mathbb{N}$ heißt explizite Form von $f$.

Links

• Catalan-Zahlen
• DS_vollständiger_foliensatz.pdf