Rekursjon i IN1010 betyr rekursjon gjennom en lenket liste

Det er verdt å si dette rett ut, for mange øver feil: fakultet og Fibonacci har jeg ikke funnet i ett eneste av de seksten eksamenssettene. Det som derimot står der hvert eneste år, er varianter av «Skriv metoden maksVekt rekursivt», «Skriv en rekursiv løsning for å sjekke at alle objektene i toget har samme sporvidde», «Skriv metoden finnMaksfartR som finner kolonnens maksimale fart ved å kalle en rekursiv metode i klassen Bil». Alt sammen er gjennomløping av en lenket liste, uten løkke. Oppgaven er verdt 8 til 11 poeng.

De to delene

Enhver rekursiv metode består av en rekursjonsbunn (tilfellet som løses uten flere kall) og et rekursivt steg (som løser et mindre problem og bygger svaret av resultatet). I en lenket liste er bunnen alltid «neste == null», og det mindre problemet er alltid «resten av lista».

// i klassen Fly
int maksVektResten() {
    if (neste == null) return mtow;                  // bunn: bare meg selv
    int restensMaks = neste.maksVektResten();        // løs resten
    return Math.max(mtow, restensMaks);              // kombiner
}

Merk at metoden ligger inne i dataobjektet og kaller seg selv på neste. Det er UiO-stilen, og sensorveiledningene beskriver den eksplisitt: «Metoden i klassen Kolonne må kalle den rekursive metoden i det første objektet i listen … Hele listen må løpes gjennom, og den laveste maksfarten finnes når rekursjonen trekker seg tilbake.» Legg merke til den siste setningen: arbeidet gjøres på vei opp.

Startermetoden

Beholderen har alltid en enkel metode som starter rekursjonen og håndterer tom liste. Sensorveiledningene ber om nøyaktig dette, og det gir poeng i seg selv.

// i klassen Flyformasjon
Integer maksVekt() {
    if (forste == null) return null;      // tom liste
    return forste.maksVektResten();
}

Her brukes Integer som returtype slik at null er mulig — flere eksamenssett ber uttrykkelig om «returner null hvis gruppen er tom». Er det ikke krav om null, kan du bruke int og for eksempel kaste et unntak eller returnere 0 for tom liste; det viktige er at tilfellet er behandlet.

Ned eller opp: hvor gjør du jobben?

Det finnes to grunnmønstre, og de gir ulik rekkefølge på utskrift. På vei ned gjør du arbeidet før det rekursive kallet:

void skrivFramover() {
    System.out.println(id);
    if (neste != null) neste.skrivFramover();
}

På vei opp gjør du arbeidet etter kallet, og da kommer elementene i motsatt rekkefølge:

void skrivBaklengs() {
    if (neste != null) neste.skrivBaklengs();
    System.out.println(id);
}

Dette er verdt å forstå, for det er nøyaktig samme innsikt som gjør at maksVektResten ovenfor må sammenligne etter kallet. Får du i oppgave å skrive lista baklengs uten å bruke forrige-pekerne, er den andre varianten svaret.

Rekursjon som leter og returnerer this

V2022 hadde en fin variant: en rekursiv metode inne i Bil som spør brukeren om han vil låne denne bilen, og returnerer bilen selv hvis svaret er ja. Sensorveiledningen: «Når en bil er funnet, returnerer metoden med verdien this.»

// i klassen Bil
Bil finnBilR(Dialog dialog, boolean kunElektrisk) {
    if (!kunElektrisk || this instanceof Elektrisk) {
        if (dialog.svarJaEllerNei("Vil du låne " + this + "?")) {
            return this;                       // treff
        }
    }
    if (neste == null) return null;            // bunn: ingen flere biler
    return neste.finnBilR(dialog, kunElektrisk);
}

Legg merke til at det er to returpunkter før det rekursive kallet: ett for treff og ett for enden av lista. Bunnen er «ingen flere elementer», og da er svaret null.

Rekursjon som kaster unntak

// i klassen Skinnegaende
void sjekkResten() throws FeilSporvidde {
    if (neste == null) return;
    if (neste.hentSporvidde() != sporvidde) {
        throw new FeilSporvidde("Ulik sporvidde ved " + neste.hentId());
    }
    neste.sjekkResten();
}

Her er svaret «ingenting» når alt er i orden, og unntaket er selve resultatet når noe er galt. Unntaket forplanter seg oppover gjennom alle de aktive kallene helt ut til den som startet rekursjonen — du trenger ikke gjøre noe spesielt for at det skal skje.

Rekursiv hjelpemetode med parameter

Noen ganger trenger rekursjonen mer informasjon enn objektet selv har. Da lager du en hjelpemetode med ekstra parametere. Sensorveiledningen for V2023 nevner nettopp denne varianten: «finne sporvidden til det første objektet i listen, og så bruke dette som parameter til den rekursive metoden som sjekker resten».

// i klassen Tog
void sjekkAlle() throws FeilSporvidde {
    if (forste != null) sjekkFra(forste, forste.hentSporvidde());
}

private void sjekkFra(Skinnegaende p, int normal) throws FeilSporvidde {
    if (p == null) return;
    if (p.hentSporvidde() != normal) throw new FeilSporvidde(p.hentId());
    sjekkFra(p.neste, normal);
}

Sensorveiledningen sier uttrykkelig at «det er OK at metoden bruker en rekursiv hjelpemetode». Bruk det når det gjør koden enklere.

Kall-stakken og hva som kan gå galt

Hvert rekursive kall legger en ny stakkramme på kall-stakken, med metodens parametere og lokale variabler. Rammene fjernes etter hvert som kallene returnerer. En liste med tusen elementer gir tusen samtidige rammer — helt uproblematisk. Men glemmer du rekursjonsbunnen, eller flytter du deg aldri framover, vokser stakken til den er full, og du får StackOverflowError. Det er en Error, ikke et Exception, og skal ikke fanges — den betyr at koden er feil.

Java optimaliserer ikke halerekursjon (det vil si et rekursivt kall som er det aller siste som skjer). I språk som gjør det, gjenbrukes stakkrammen; i Java bygges den opp uansett. Praktisk konsekvens: en rekursiv gjennomløping av en liste med hundretusener av elementer kan velte i Java, mens en while-løkke går fint. På eksamen er listene små, så velg den formen oppgaven ber om.

Rekursjon over array og over dobbeltlenket liste

static int sum(int[] a, int i) {
    if (i == a.length) return 0;         // bunn: forbi siste indeks
    return a[i] + sum(a, i + 1);
}

For en array er indeksen det som «krymper»; bunnen er at indeksen har passert enden. For en dobbeltlenket liste er rekursjonen nøyaktig som for en enkeltlenket — forrige-pekeren gir deg bare muligheten til å rekursere baklengs fra siste i stedet.

Studieguide: Rekursjon