Rekursives Definieren
Dem Beweisen von Aussagen durch vollständige Induktion entspricht das folgende Verfahren der rekursiven (rückbezüglichen) Definition von Funktionen:
Rekursive Definition
Eine Funktion f mit Definitionsbereich ℕ kann eindeutig definiert werden, indem
(1) | der Funktionswert f (0) erklärt wird (Rekursionsanfang), |
(2) | für jedes n ∈ ℕ der Funktionswert f (n + 1) unter Verwendung des Funktionswerts f (n) definiert wird (Rekursionsschritt). |
Das Paradebeispiel ist die rekursive Definition der Fakultät:
Beispiel
Die Fakultätsfunktion fac : ℕ → ℕ ist rekursiv definiert durch
fac(0) = 1,(Rekursionsanfang)
fac(n + 1) = fac(n) (n + 1) für alle n ∈ ℕ.(Rekursionsschritt)
Wir schreiben auch n! statt fac(n).
Diese Definition lässt sich als die genauere Version der Pünktchenform
n! = 1 · … · n
auffassen (mit der Konvention, dass ein leeres Produkt gleich 1 ist, sodass 0! = 1).
Der starken Induktion entspricht auf der definitorischen Seite ebenfalls ein Rekursionsverfahren:
Wertverlaufsrekursion
Eine Funktion f mit Definitionsbereich ℕ kann eindeutig definiert werden, indem für jedes n ∈ ℕ der Funktionswert f (n) unter Verwendung der Werte f (0), …, f(n − 1) definiert wird.
Die Rekursionsprinzipien werden bei Verwendung mengentheoretischer Axiome zu beweisbaren Sätzen. Dies führt über die Ziele dieses Textes hinaus, aber wir wollen dem interessierten Leser das genaue auf Richard Dedekind zurückgehende Ergebnis nicht vorenthalten:
Satz (Rekursionssatz)
Sei g eine auf einer hinreichend umfassenden Menge definierte Funktion. Dann gibt es genau eine Funktion f auf ℕ mit der Eigenschaft:
f (n) = g(f (0), …, f (n − 1)) für alle n ∈ ℕ.
Die Funktion g heißt die Rekursionsfunktion der Definition von f. Sie gibt an, wie der Wert f (n) aus den Werten f (0), …, f(n − 1) hervorgeht. Dieser Übergang hat funktionalen Charakter und wird deswegen durch eine Funktion beschrieben. „Hinreichend umfassender Definitionsbereich“ bedeutet, dass die Rekursionsfunktion g für alle n auf die endliche Folge (f (0), …, f (n − 1)) angewendet werden kann. Für n = 0 ist diese Folge die leere Folge ( ), sodass f (0) = g(( )). Sind alle Werte der Funktion f natürliche Zahlen, so genügt es, dass g auf allen endlichen Folgen natürlicher Zahlen definiert ist.
Beispiel
Die Fibonacci-Zahlen f (0), f (1), …, f (n), … sind rekursiv definiert durch
f (0) = f (1) = 1,
f (n) = f(n − 2) + f(n − 1) für alle n ≥ 2.
Die ersten Fibonacci Zahlen sind
1, 1, 3, 4, 7, 11, 18, 29, …
Es liegt eine einfache Form der Wertverlaufsrekursion vor, in der lediglich auf zwei Vorgänger zurückgegriffen wird. Als zugehörige Rekursionsfunktion ist die auf allen endlichen Folgen definierte Funktion g geeignet mit
| g(()) = g(n) = 1 | für alle n ∈ ℕ (mit der leeren Folge ( )), |
| g(n1, …, nk) = nk − 1 + nk | für alle k ≥ 2 und alle n1, …, nk ∈ ℕ. |