Rekursions-Grundlagen

Teil des Abschnitts Fundamentals der C-Journey von Coddy — Lektion 50 von 63.

Rekursion ist eine Technik, bei der eine Funktion sich selbst aufruft, um ein Problem zu lösen. Es ist so, als würde man ein großes Problem lösen, indem man es in kleinere, ähnliche Probleme zerlegt.

Schauen wir uns eine einfache rekursive Funktion an, die die Fakultät berechnet:

int factorial(int n) {
    // Basisfall: Fakultät von 0 oder 1 ist 1
    if (n <= 1) {
        return 1;
    }
    
    // Rekursiver Fall: n! = n * (n-1)!
    return n * factorial(n - 1);
}

Jede rekursive Funktion benötigt:

Einen Basisfall, um die Rekursion zu beenden
Einen Rekursionsfall, der sich auf den Basisfall zubewegt

Zum Beispiel die Berechnung von factorial(3):

factorial(3) ruft factorial(2) auf
factorial(2) ruft factorial(1) auf
factorial(1) gibt 1 zurück (Basisfall)

factorial(2) gibt 2 * 1 = 2 zurück
factorial(3) gibt 3 * 2 = 6 zurück

Aufgabe

Einfach

Erstellen Sie eine Funktion namens sumToN, die Rekursion verwendet, um die Summe der Zahlen von 1 bis n zu berechnen.

Zum Beispiel:

sumToN(3) sollte 6 zurückgeben (1 + 2 + 3)
sumToN(5) sollte 15 zurückgeben (1 + 2 + 3 + 4 + 5)

Ihre Funktion sollte:

Einen Basisfall verwenden, wenn n gleich 1 ist (1 zurückgeben)
Andernfalls n plus die Summe der Zahlen von 1 bis (n-1) zurückgeben

Spickzettel

Rekursion ist eine Technik, bei der eine Funktion sich selbst aufruft, um ein Problem zu lösen, indem sie es in kleinere, ähnliche Probleme zerlegt.

Jede rekursive Funktion benötigt:

Einen Basisfall, um die Rekursion zu beenden
Einen rekursiven Fall, der sich auf den Basisfall zubewegt

Beispiel – Fakultätsfunktion:

int factorial(int n) {
    // Basisfall: Fakultät von 0 oder 1 ist 1
    if (n <= 1) {
        return 1;
    }
    
    // Rekursiver Fall: n! = n * (n-1)!
    return n * factorial(n - 1);
}

Wie factorial(3) ausgeführt wird:

factorial(3) ruft factorial(2) auf
factorial(2) ruft factorial(1) auf
factorial(1) gibt 1 zurück (Basisfall)
factorial(2) gibt 2 * 1 = 2 zurück
factorial(3) gibt 3 * 2 = 6 zurück

Probier es selbst

#include <stdio.h>

// Schreibe deine sumToN-Funktion hier

// Ändere die main()-Funktion nicht
int main() {
    int n;
    scanf("%d", &n);
    
    printf("%d", sumToN(n));
    return 0;
}

Teste dich selbst

Diese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.

Alle Lektionen in Fundamentals

1Einführung

Die Programmiersprache C Hello World!Kommentare Grundlegende Programmstruktur

4Kontrollfluss

If-Anweisung If - Else Else-If Switch Case Ternärer Bedingungsoperator Recap-Challenge Verschachteltes If - Else

7Funktionen

Eine Funktion deklarieren Rückgabetypen Parameter Wiederholungs-Challenge #1Rekursions-GrundlagenFunktionsprototypen Wiederholungs-Challenge #2