C Academy · Lektion

Klassische Rekursionsprobleme

Fakultät und Fibonacci.

Klassische Rekursionsprobleme ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.

Klassische Probleme

Manche Probleme eignen sich ganz natürlich für Rekursion. Wenn Sie die klassischen Beispiele lernen, erhalten Sie Muster, die Sie wiederverwenden können.

In dieser Lektion behandeln wir Fakultät, Fibonacci-Zahlen, Ziffernsumme, größten gemeinsamen Teiler und die Umkehrung einer Ausgabe.

Fakultät

Die Fakultät von n ist n mal der Fakultät von n minus 1, wobei 1! gleich 1 ist.

Dies ist ein Beispiel für textbookmäßige Rekursion: ein klarer Basisfall und ein rekursiver Aufruf.

#include <stdio.h>

long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

int main(void) {
    printf("%ld\n", factorial(6));
    return 0;
}

Fibonacci-Zahlen

Jede Fibonacci-Zahl ist die Summe der beiden vorherigen. Die rekursive Definition benötigt zwei Basisfälle: fib(0)=0 und fib(1)=1.

Diese Variante führt pro Schritt zwei Aufrufe aus.

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

Fibonacci ausführen

Hier ist das vollständige Programm. fib(10) sollte 55 ausgeben.

Beachten Sie, dass diese naive Variante Berechnungen wiederholt und deshalb für große n langsam ist.

#include <stdio.h>

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    printf("%d\n", fib(10));
    return 0;
}

Ziffern summieren

Um die Ziffern einer Zahl zu addieren, ermitteln Sie die letzte Ziffer mit n % 10 und wenden die Rekursion mit dem Rest n / 10 an.

Der Basisfall ist erreicht, wenn n den Wert 0 erreicht.

int digit_sum(int n) {
    if (n == 0) return 0;
    return (n % 10) + digit_sum(n / 10);
}

Die Ziffernsumme in Aktion

Für 1234 beträgt die Summe 1+2+3+4 = 10. Lassen Sie uns dies mit einem vollständigen Programm überprüfen.

#include <stdio.h>

int digit_sum(int n) {
    if (n == 0) return 0;
    return (n % 10) + digit_sum(n / 10);
}

int main(void) {
    printf("%d\n", digit_sum(1234));
    return 0;
}

Größter gemeinsamer Teiler

Euklids Algorithmus eignet sich ganz natürlich für Rekursion. Der größte gemeinsame Teiler von a und b ist gleich dem größten gemeinsamen Teiler von b und a % b.

Wenn b zu 0 wird, ist a das Ergebnis.

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

Vollständiges GGT-Programm

Der größte gemeinsame Teiler von 48 und 18 ist 6. Dieses Programm gibt ihn aus.

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main(void) {
    printf("%d\n", gcd(48, 18));
    return 0;
}

Eine Zahl umkehren

Rekursion kann auch die Ausgabe steuern. Wenn Sie die letzte Ziffer erst nach dem rekursiven Aufruf ausgeben, kehren Sie die Verarbeitungsreihenfolge auf natürliche Weise um.

Dieser Helfer gibt mithilfe von Rekursion jede Ziffer einer Zahl in einer eigenen Zeile aus.

#include <stdio.h>

void print_digits(int n) {
    if (n == 0) return;
    print_digits(n / 10);
    printf("%d ", n % 10);
}

int main(void) {
    print_digits(729);
    printf("\n");
    return 0;
}

Potenzfunktion

Auch das Potenzieren einer Basis mit einem Exponenten ist rekursiv: base^exp entspricht base mal base^(exp-1).

Der Basisfall ist der Exponent 0, für den 1 zurückgegeben wird.

long power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

Muster, die Sie wiederverwenden werden

Beachten Sie die gemeinsame Struktur: Prüfen Sie den Basisfall und verknüpfen Sie anschließend den aktuellen Schritt mit dem Ergebnis eines kleineren Aufrufs.

Sobald Sie dieses Muster erkennen, lassen sich viele Probleme durch kurze rekursive Funktionen lösen.

Kurztest

Wählen Sie die richtigen Basisfälle aus.

Zusammenfassung

Fakultät, Fibonacci, Ziffernsumme, GGT und Potenz folgen demselben rekursiven Muster: Behandeln Sie den Basisfall und verknüpfen Sie anschließend den aktuellen Wert mit einem kleineren Teilproblem.

Diese Vorlagen lassen sich auf viele andere Aufgaben übertragen.

Häufig gestellte Fragen

Ist die Lektion „Klassische Rekursionsprobleme“ kostenlos?

Ja — der vollständige Text von „Klassische Rekursionsprobleme“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Klassische Rekursionsprobleme“?

Fakultät und Fibonacci. Du übst C Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um C Academy zu starten?

Keine Vorkenntnisse erforderlich. C Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.

Wie lange dauert die Lektion „Klassische Rekursionsprobleme“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser C Academy-Lektion Code schreiben und ausführen?

Ja. Jede C Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

← Zurück zu C Academy