C Academy · Lektion

Rekursion kontra iteration

Hvornår De bør vælge hver metode.

Lektion 3 af 413 trin

Rekursion kontra iteration er en gratis C Academy-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i C Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. C Academy-kurset indeholder 4 lektioner i alt.

To måder at gentage på

Mange problemer kan løses med enten rekursion eller iteration. Iteration bruger løkker, mens rekursion bruger funktionskald.

Begge kan give det samme resultat, men de adskiller sig med hensyn til stil, hukommelsesforbrug og hastighed.

Fakultet med en løkke

Her er fakultet skrevet iterativt med en for-løkke. Funktionen kalder ikke sig selv; en enkelt variabel opsamler produktet.

#include <stdio.h>

long factorial(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++)
        result *= i;
    return result;
}

int main(void) {
    printf("%ld\n", factorial(6));
    return 0;
}

Fakultet med rekursion

Den rekursive version er kortere og afspejler den matematiske definition direkte.

Begge udskriver 720 for factorial(6), men de bruger forskellige mekanismer.

long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

Forskelle i hukommelse

Iteration bruger normalt en fast og lille mængde hukommelse: blot nogle få lokale variabler.

Rekursion tilføjer en stakramme for hvert kald, så dyb rekursion bruger mere hukommelse og kan løbe tør for stakplads.

Forskelle i hastighed

Hvert rekursive kald har en lille omkostning: Der skal oprettes en ramme, og der skal returneres fra den.

Til simple tælleopgaver er løkker ofte en smule hurtigere, fordi de undgår denne kalds-overhead.

Når rekursion er bedst

Rekursion er særlig velegnet, når problemet naturligt er rekursivt, f.eks. træer, indlejrede strukturer eller del-og-hersk-algoritmer.

I sådanne tilfælde er rekursiv kode kortere og tydeligere end den tilsvarende løkke med en manuel stak.

Når iteration er bedst

Ved enkel lineær gentagelse, f.eks. når du summerer et array eller tæller, er en løkke enklere og bruger konstant hukommelse.

Den undgår også risikoen for stakoverløb ved store input.

int sum_array(int a[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++)
        total += a[i];
    return total;
}

Samme opgave, begge stilarter

Du kan summere 1 til n på begge måder. Her er den iterative version, som returnerer det samme svar som rekursion.

#include <stdio.h>

int sum_to(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++)
        total += i;
    return total;
}

int main(void) {
    printf("%d\n", sum_to(100));
    return 0;
}

Konvertering fra rekursion til en løkke

Al rekursion kan omskrives til iteration, nogle gange ved hjælp af din egen eksplicitte stak.

Enkel lineær rekursion, f.eks. fakultet eller sum, kan konverteres til en almindelig løkke med en akkumulatorvariabel.

#include <stdio.h>

int main(void) {
    int n = 5, result = 1;
    while (n > 1) { result *= n; n--; }
    printf("%d\n", result);
    return 0;
}

Bemærkning om halerekursion

Et halerekursivt kald er den sidste handling i en funktion. Nogle compilere optimerer det til en løkke ved at genbruge én ramme.

C garanterer ikke dette, så du må ikke regne med det ved dyb rekursion.

int sum_tail(int n, int acc) {
    if (n == 0) return acc;
    return sum_tail(n - 1, acc + n);
}

Valg af fremgangsmåde

Spørg dig selv: Er problemet naturligt indlejret eller baseret på del-og-hersk? Så passer rekursion godt.

Er det en enkel lineær gentagelse med muligvis meget stort input? Så er iteration mere sikker og ofte hurtigere.

Hurtig kontrol

Sammenlign de to fremgangsmåder.

Besvar den i den interaktive lektion

Opsummering

Rekursion og iteration kan løse de samme problemer. Løkker bruger konstant hukommelse og er velegnede til lineære opgaver; rekursion er tydeligere ved indlejrede problemer og del-og-hersk-problemer, men koster en stakramme pr. kald.

Gratis at komme i gang

Lær C med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser: 39
Lektioner: 144

Start gratis Se hele kurset

Ofte stillede spørgsmål

Er lektionen “Rekursion kontra iteration” gratis?

Ja — hele teksten til “Rekursion kontra iteration” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af C Academy-kurset, skal du opgradere til CoddyKit PRO. C Academy-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Rekursion kontra iteration”?

Hvornår De bør vælge hver metode. Du øver dig i C Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på C Academy?

Der kræves ingen tidligere erfaring. C Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.

Hvor lang tid tager lektionen “Rekursion kontra iteration”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne C Academy-lektion?

Ja. Alle C Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

← Tilbage til C Academy