Rekurencja w C

Rekurencja to technika, w której funkcja wywołuje samą siebie, aby rozwiązać problem.

W tej lekcji dowie się Pan/Pani:

• Czym jest rekurencja i jak działa.
• Jak implementować funkcje rekurencyjne.
• Czym różnią się rekurencja i iteracja.

Czym jest rekurencja?

Rekurencja występuje wtedy, gdy funkcja wywołuje samą siebie, aby rozwiązać mniejszą część problemu.

Przykładowa składnia:

void function() { function(); // Recursive call }

Każda funkcja rekurencyjna musi mieć przypadek bazowy, aby zapobiec nieskończonej rekurencji.

Przykład: rekurencja

Ten program demonstruje rekurencję, wyświetlając liczby od 5 do 1.

#include <stdio.h>

void countDown(int n) {
    if (n <= 0) return; // Base case
    printf("%d\n", n);
    countDown(n - 1); // Recursive call
}

int main() {
    countDown(5);
    return 0;
}

Przypadek bazowy w rekurencji

Funkcja rekurencyjna musi zawierać przypadek bazowy, który zatrzymuje rekurencję.

Przykład:

if (n == 0) return;

Bez przypadku bazowego funkcja będzie wywoływać samą siebie w nieskończoność, powodując przepełnienie stosu.

Przykład: silnia z użyciem rekurencji

Ten program oblicza silnię liczby za pomocą rekurencji.

#include <stdio.h>

int factorial(int n) {
    if (n == 0) return 1; // Base case
    return n * factorial(n - 1);
}

int main() {
    printf("Factorial of 5: %d\n", factorial(5));
    return 0;
}

Rekurencja a iteracja

Rekurencja i iteracja (pętle) mogą prowadzić do tych samych rezultatów, ale działają w różny sposób.

Różnice:

• Rekurencja korzysta z wywołań funkcji i wymaga więcej pamięci.
• Iteracja korzysta z pętli i zazwyczaj jest wydajniejsza.
• Rekurencja upraszcza kod w przypadku problemów takich jak przechodzenie po drzewie.

Przykład: ciąg Fibonacciego (rekurencyjnie)

Ten program oblicza ciąg Fibonacciego za pomocą rekurencji.

#include <stdio.h>

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

int main() {
    printf("Fibonacci(5): %d\n", fibonacci(5));
    return 0;
}

Kiedy stosować rekurencję?

Rekurencja jest przydatna w problemach obejmujących:

• Przechodzenie po drzewie.
• Przeszukiwanie z nawrotami (np. rozwiązywanie labiryntów).
• Problemy matematyczne, takie jak obliczanie silni i ciągu Fibonacciego.

Podsumowanie

W tej lekcji nauczyli się Państwo:

• Czym jest rekurencja i jak działa.
• Jakie znaczenie ma przypadek bazowy.
• Czym różnią się rekurencja i iteracja.

Następnie poznają Państwo tablice i napisy w języku C!