Föreläsning 8: Rekursiva tankar

Rekursiva dumsvar

Framöver kommer vi ägna oss åt begreppet rekursivt anrop, alltså när en metod anropar sej själv. Det påminner om när man i vardagslivet besvarar en fråga på ett sätt som framtvingar en liknande fråga som i sin tur besvaras på ett sätt som framtvingar en liknande fråga etc. Exempel:
Fråga: Hur många år fyller du i år?
Rekursivt svar: Ett år mer än i fjol.
Om man ger sådana dumsvar blir man inte populär, men faktum är att det går utmärkt att programmera på det sättet. Dock måste man se till att rekursionen avslutas när man kommer ner till något enkelt basfall. I mitt fall skulle jag behöva komplettera dumsvaret så här:
...men år 1973 var jag noll år.

Med javakoden nedan skulle anropet age(2000) ge värdet 27.

    public static int age(int year) {
	if (year == 1973) 
	    return 0;
	else 
	    return 1 + age(year - 1);
    }

Rekursiva anrop

Många undrar hur datorn gör när den får fram värdet 27 i exemplet ovan. Egentligen ska man inte bekymra sej om det! Om den rekursiva tanken är korrekt, så kommer datorn att räkna fram rätt värde. Men för den som envisas med att vilja veta vad som händer kommer här den sanna beskrivningen.

Anropet age(2000) ger så småningom upphov till anropet age(1999). Vid anropet av age(1999) avbryts tillfälligt exekveringen av age(2009). age(1999) får eget minne och börjar exekvera. I det egna minnet finns variabeln year som sätts till 1999, allt medan original-age()s year fortsätter att vara 2000. Så småningom har 27 olika age() anropats och alla är tillfälligt avbrutna i väntan på att den anropade age() ska komma tillbaka med ett siffervärde. Och det tjugoåttonde anropet, age(0) returnerar verkligen genast värdet 0. Då kan den föregående age() slutföra beräkningen 1 + 0 och returnera värdet 1, etc. Slutligen kan original-age() returnera värdet 27 till huvudprogrammet, som inte har någon aning om hur mycket arbete som skett bakom kulisserna!

Sifferexempel

Fråga: Hur många siffror har heltalet n?
Rekursivt svar: En siffra mer än om man stryker sista siffran i n, ...men tal mindre än tio är ensiffriga.
    public static int nDigits(int n) {
	if (n < 10) 
	    return 1;
	return 1 + nDigits(n / 10);
    }

Fråga: Vilken siffersumma har heltalet n?
Rekursivt svar: Sista siffran plus siffersumman om man stryker sista siffran i n, ...men noll har siffersumman noll.
    public static int sumOfDigits(int n) {
	if (n == 0)
	    return 0;
	return (n % 10) + sumOfDigits(n / 10);
    }

Fråga: Hur skriver man talet n binärt?
Rekursivt svar: Först skriver man n/2 binärt och sen skriver man en nolla eller etta beroende på om n var jämnt eller udda, ...men talen 0 och 1 skrivs likadant binärt.
    public static void writeBinary(int n) {
	if (n == 0 || n == 1)
	    System.out.print(n);
	else { 
	    writeBinary(n / 2); 
	    System.out.print(n % 2);
	}
    }

Listexempel

Vi tänker oss en länkad lista av objekt, där varje objekt innehåller ett tal och en next-pekare. Variabeln top pekar på den översta posten.
Fråga: Hur många poster finns i stacken?
Rekursivt svar: En post mer än i stacken under topposten ...men en tom stack har noll poster.
    // I stack-klassen...
    public int nElements() {
	return nElements(top);
    }

    private int nElemenst(Node p) {
	if (p == null)
	    return 0;
	return 1 + nElements(p.next);
    }

Anropet stack.nElements() ger nu rätt svar!

Kör exemplet!

Kopiera filerna Rekursion.java och IntStack2.java, kompilera och provkör programmet Rekursion.

^ Upp till kurssidan.


Sidansvarig: <efo@nada.kth.se>
Senast ändrad 19 november 2000
Tekniskt stöd: <webmaster@nada.kth.se>