Rekursion

Rekursive Definitionen

Die Fakultät

Die Fakultät einer natürlichen Zahl $n$ ist das Produkt der natürlichen Zahlen von 1 bis $n$: $n! = 1 \cdot 2 \cdots n$, mit der Konvention $0! = 1$. Die Auslassungspunkte dieser Formel verbergen eine Schleife, und die Lektion Schleifen hat gezeigt, wie man sie schreibt. Nun lässt dieselbe Definition eine andere Form zu, die keine Schleife erwähnt: Die Fakultät von $n$ ist $n$ mal die Fakultät von $n - 1$, und die von 0 ist 1.

Das ist eine rekursive Definition: Sie definiert die Fakultät von $n$ mithilfe der Fakultät einer kleineren Zahl. Sie ist nicht zirkulär, denn jede Anwendung der zweiten Regel steigt eine Stufe hinab, und die Treppe endet bei der ersten: $3! = 3 \cdot 2! = 3 \cdot 2 \cdot 1! = 3 \cdot 2 \cdot 1 \cdot 0! = 6$. Die beiden Regeln haben Namen. Die erste ist der Basisfall, der das Ergebnis liefert, ohne sich auf etwas anderes zu beziehen; die zweite ist der Rekursionsfall, der das Problem auf eine kleinere Instanz desselben Problems zurückführt.

C++ erlaubt einer Funktion, sich selbst aufzurufen, und damit lässt sich die Definition fast Wort für Wort übertragen.

#include <print>​// Fakultät von n.// Vorbedingung: 0 <= n <= 12 (die Schranke wird später begründet).// Nachbedingung: gibt n! = 1 · 2 · ... · n zurück, mit 0! = 1.int factorial(int n){    if (n == 0) {        return 1;                   // Basisfall    }    return n * factorial(n - 1);    // Rekursionsfall}​int main(){    for (int n{0}; n <= 6; ++n) {        std::println("{}! = {}", n, factorial(n));    }}

0! = 11! = 12! = 23! = 64! = 245! = 1206! = 720

Der Vertrag ist keine Zierde: Mit $n = -1$ würde der Rekursionsfall mit $-2$ aufrufen, danach mit $-3$, und nie die 0 erreichen; und $13!$ passt nicht in einen int. Viele einführende Texte schreiben diese Fakultät mit dem Basisfall if (n == 0 || n == 1), redundant, aber harmlos, und ohne etwas über negative Zahlen oder die Größe des Ergebnisses zu sagen: Ihr Code terminiert nicht bei $n < 0$ und liefert ein sinnloses Ergebnis ab $13!$. Beide Mängel werden weiter unten an ihrer Stelle untersucht.

Basisfall und Rekursionsfall

Jede rekursive Funktion hat einen oder mehrere Basisfälle, die direkt gelöst werden, und einen oder mehrere Rekursionsfälle, die dieselbe Funktion mit einem in einem genauen Sinn kleineren Argument aufrufen und das Zurückgegebene weiterverarbeiten.

Die Potenz $x^n$, mit natürlichem $n$, wird durch $x^0 = 1$ und $x^n = x \cdot x^{n - 1}$ definiert: Die Größe ist der Exponent. Die Ziffernsumme einer natürlichen Zahl $n$ (die von 2026 ist $2 + 0 + 2 + 6 = 10$) wird so definiert: Ist $n < 10$, so ist die Summe $n$, denn die Zahl hat nur eine Ziffer; andernfalls ist sie die Ziffernsumme von $\lfloor n / 10 \rfloor$, also von $n$ ohne seine letzte Ziffer, plus diese letzte Ziffer, $n \bmod 10$. Hier ist die Größe die Anzahl der Ziffern.

#include <print>​// x hoch n.// Vorbedingung: n >= 0.// Nachbedingung: gibt x^n zurück, mit x^0 = 1.double power(double x, int n){    if (n == 0) {        return 1.0;    }    return x * power(x, n - 1);}​// Summe der Dezimalziffern von n.// Vorbedingung: n >= 0.// Nachbedingung: gibt die Ziffernsumme von n zurück.int digitSum(int n){    if (n < 10) {        return n;    }    return digitSum(n / 10) + n % 10;}​int main(){    std::println("2^10 = {}", power(2.0, 10));    std::println("1.5^3 = {}", power(1.5, 3));    std::println("Ziffernsumme von 2026: {}", digitSum(2026));}

2^10 = 10241.5^3 = 3.375Ziffernsumme von 2026: 10

Eine rekursive Funktion zu schreiben heißt also, zwei Fragen zu beantworten: welche Fälle ohne Hilfe gelöst werden und wie man die Lösung eines Falls aus der eines kleineren gewinnt. Sind beide Antworten richtig, so ist es auch die Funktion, und das Folgende beweist es.