Podstawy rekurencji

Część sekcji Podstawy ścieżki C w Coddy. Lekcja 50 z 63.

Rekurencja to technika, w której funkcja wywołuje samą siebie, aby rozwiązać problem. To jak rozwiązywanie dużego problemu przez podzielenie go na mniejsze, podobne problemy.

Przyjrzyjmy się prostej funkcji rekurencyjnej, która oblicza silnię:

int factorial(int n) {
    // Przypadek bazowy: silnia z 0 lub 1 wynosi 1
    if (n <= 1) {
        return 1;
    }
    
    // Przypadek rekurencyjny: n! = n * (n-1)!
    return n * factorial(n - 1);
}

Każda funkcja rekurencyjna potrzebuje:

Przypadku bazowego, który zatrzymuje rekurencję
Przypadku rekurencyjnego, który zbliża do przypadku bazowego

Na przykład obliczanie factorial(3):

factorial(3) wywołuje factorial(2)
factorial(2) wywołuje factorial(1)
factorial(1) zwraca 1 (przypadek bazowy)

factorial(2) zwraca 2 * 1 = 2
factorial(3) zwraca 3 * 2 = 6

Wyzwanie

Łatwy

Utwórz funkcję o nazwie sumToN, która używa rekurencji do obliczania sumy liczb od 1 do n.

Na przykład:

sumToN(3) powinno zwrócić 6 (1 + 2 + 3)
sumToN(5) powinno zwrócić 15 (1 + 2 + 3 + 4 + 5)

Twoja funkcja powinna:

Użyć przypadku bazowego, gdy n wynosi 1 (zwrócić 1)
W przeciwnym razie zwrócić n plus sumę liczb od 1 do (n-1)

Spróbuj swoich sił

#include <stdio.h>

// Napisz tutaj swoją funkcję sumToN

// Nie zmieniaj funkcji main()
int main() {
    int n;
    scanf("%d", &n);
    
    printf("%d", sumToN(n));
    return 0;
}

Sprawdź się

Ta lekcja zawiera krótki quiz. Zacznij lekcję, żeby na niego odpowiedzieć i śledzić swoje postępy.

Wszystkie lekcje w sekcji Podstawy

1Wprowadzenie

Język C Witaj, świecie!Komentarze Podstawowa struktura programu

4Sterowanie przepływem

Instrukcja if If - else Else-if Instrukcja switch-case Operator warunkowy (ternary)Wyzwanie podsumowujące Zagnieżdżone if - else

7Funkcje

Deklarowanie funkcji Typy zwracane Parametry Powtórka – wyzwanie nr 1Podstawy rekurencjiPrototypy funkcji Powtórka – wyzwanie nr 2

Poćwicz samodzielnie: Kompilator C online