Rekursjon i C

Rekursjon er en teknikk der en funksjon kaller seg selv for å løse et problem.

I denne leksjonen lærer De:

• Hva rekursjon er, og hvordan den fungerer.
• Hvordan De implementerer rekursive funksjoner.
• Forskjellen mellom rekursjon og iterasjon.

Rekursjon oppstår når en funksjon kaller seg selv for å løse en mindre del av et problem.

Eksempel på syntaks:

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

Alle rekursive funksjoner må ha et basistilfelle for å forhindre uendelig rekursjon.

Dette programmet demonstrerer rekursjon ved å skrive ut 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 funksjon må inneholde et basistilfelle for å stoppe rekursjonen.

Eksempel:

if (n == 0) return;

Uten et basistilfelle vil funksjonen kalle seg selv uendelig mange ganger, noe som fører til stack overflow.

Dette programmet beregner fakultetet til et tall ved hjelp av rekursjon.

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

Rekursjon og iterasjon (løkker) kan gi samme resultat, men fungerer på ulike måter.

Forskjeller:

• Rekursjon bruker funksjonskall og krever mer minne.
• Iterasjon bruker løkker og er vanligvis mer effektiv.
• Rekursjon gjør koden enklere for problemer som traversering av trær.

Dette programmet beregner Fibonacci-følgen ved hjelp av rekursjon.

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

Rekursjon er nyttig for problemer som omfatter:

• Traversering av trær.
• Backtracking (for eksempel løsning av labyrinter).
• Matematiske problemer som fakultet og Fibonacci.

I denne leksjonen har du lært:

• Hva rekursjon er, og hvordan det fungerer.
• Hvor viktig et basistilfelle er.
• Forskjellen mellom rekursjon og iterasjon.

Deretter skal vi utforske tabeller og strenger i C!