C Academy · leksjon

Rekursjon kontra iterasjon

Når De bør velge hver av dem.

Leksjon 3 av 413 trinn

Rekursjon kontra iterasjon er en gratis leksjon i C Academy på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i C Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i C Academy inneholder totalt 4 leksjoner.

To måter å gjenta på

Mange problemer kan løses enten med rekursjon eller iterasjon. Iterasjon bruker løkker, mens rekursjon bruker funksjonskall.

Begge kan gi samme resultat, men de skiller seg i stil, minnebruk og hastighet.

Fakultet med en løkke

Her er fakultet skrevet iterativt med en for-løkke. Ingen funksjon kaller seg selv; én variabel samler opp 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 rekursjon

Den rekursive versjonen er kortere og gjenspeiler den matematiske definisjonen direkte.

Begge skriver ut 720 for factorial(6), men de bruker ulike mekanismer.

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

Forskjeller i minnebruk

Iterasjon bruker vanligvis en fast og liten mengde minne: bare noen få lokale variabler.

Rekursjon legger til en stakkramme for hvert kall, så dyp rekursjon bruker mer minne og kan gå tom for stakkplass.

Forskjeller i hastighet

Hvert rekursive kall har en liten kostnad: det må settes opp en ramme, og funksjonen må returnere fra den.

For enkle telleoppgaver er løkker ofte litt raskere fordi de unngår denne kostnaden ved funksjonskall.

Når rekursjon er best

Rekursjon er spesielt nyttig når problemet naturlig er rekursivt, for eksempel med trær, nøstede strukturer eller divide-and-conquer-algoritmer.

Da er rekursiv kode kortere og tydeligere enn en tilsvarende løkke med en manuell stakk.

Når iterasjon er best

For enkel lineær gjentakelse, som å summere en tabell eller telle, er en løkke enklere og bruker konstant minne.

Den unngår også risikoen for stack overflow ved store inndata.

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

Samme oppgave, begge stiler

Det å summere fra 1 til n kan gjøres på begge måter. Her er den iterative versjonen, som returnerer samme svar som rekursjon.

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

Konvertere rekursjon til en løkke

All rekursjon kan skrives om til iterasjon, noen ganger ved å bruke en egen eksplisitt stakk.

Enkel lineær rekursjon, som fakultet eller sum, kan konverteres til en vanlig 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;
}

Om halerekursjon

Et tail-recursive kall er den siste handlingen i en funksjon. Noen kompilatorer optimaliserer det til en løkke ved å gjenbruke én ramme.

C garanterer ikke dette, så De bør ikke stole på det ved dyp rekursjon.

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

Velge en tilnærming

Spør: Er problemet naturlig nøstet eller basert på divide-and-conquer? Da passer rekursjon.

Er det enkel lineær gjentakelse med mulig svært store inndata? Da er iterasjon tryggere og ofte raskere.

Hurtigsjekk

Sammenlign de to tilnærmingene.

Besvar den i den interaktive leksjonen

Oppsummering

Rekursjon og iterasjon kan løse de samme problemene. Løkker bruker konstant minne og passer godt til lineære oppgaver. Rekursjon er tydeligere for nøstede problemer og divide-and-conquer-problemer, men koster én stakkramme per kall.

Gratis å komme i gang

Lær deg C med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 39
Leksjoner: 144

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Rekursjon kontra iterasjon» gratis?

Ja – hele teksten i «Rekursjon kontra iterasjon» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av C Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i C Academy inneholder totalt 4 leksjoner.

Hva lærer jeg i «Rekursjon kontra iterasjon»?

Når De bør velge hver av dem. Du øver på C Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med C Academy?

Ingen tidligere erfaring er nødvendig. C Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.

Hvor lang tid tar leksjonen «Rekursjon kontra iterasjon»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne C Academy-leksjonen?

Ja. Alle C Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til C Academy