Rekursion i C

Rekursion er en teknik, hvor en funktion kalder sig selv for at løse et problem.

I denne lektion lærer du:

• Hvad rekursion er, og hvordan den fungerer.
• Hvordan du implementerer rekursive funktioner.
• Forskellen mellem rekursion og iteration.

Rekursion opstår, når en funktion kalder sig selv for at løse en mindre del af et problem.

Eksempel på syntaks:

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

Alle rekursive funktioner skal have et basistilfælde for at forhindre uendelig rekursion.

Dette program demonstrerer rekursion ved at udskrive tallene fra 5 til 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;
}

En rekursiv funktion skal indeholde et basistilfælde, der stopper rekursionen.

Eksempel:

if (n == 0) return;

Uden et basistilfælde vil funktionen kalde sig selv uendeligt, hvilket medfører et stack overflow.

Dette program beregner fakultetet af et tal ved hjælp af rekursion.

#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;
}

Rekursion og iteration (løkker) kan give de samme resultater, men de fungerer forskelligt.

Forskelle:

• Rekursion bruger funktionskald og kræver mere hukommelse.
• Iteration bruger løkker og er normalt mere effektiv.
• Rekursion gør koden enklere i problemer som gennemløb af træer.

Dette program beregner Fibonacci-talrækken ved hjælp af rekursion.

#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;
}

Rekursion er nyttig til problemer, der involverer:

• Gennemløb af træer.
• Tilbagesporing (f.eks. løsning af labyrinter).
• Matematiske problemer som fakultet og Fibonacci.

I denne lektion har du lært:

• Hvad rekursion er, og hvordan den fungerer.
• Hvor vigtigt et basistilfælde er.
• Forskellen mellem rekursion og iteration.

Derefter ser du nærmere på arrays og strenge i C!