Induktion och rekursiva funktioner

För att skriva och förstå rekursiva funktioner kan man använda ett tankesätt som är intimt förknippat med matematisk induktion. Först kommer vi att introducera matematisk induktion och förklara varför metoden fungerar, sedan kommer ett antal exempel, både från matematik och programmering.

Matematisk induktion

Matematisk induktion är en enkel bevismetod som ofta kan användas för att bevisa påståenden som innehåller en heltalsparameter. Dessa påståenden kan gälla både matematik och program. Vi inför beteckningen P(n), där n ≥ 0, för ett sådant påstående.

Ett bevis för påståendet P(n) med hjälp av matematisk induktion sker i två steg.

Basfall: Först visar man att påståendet P(0) är sant.
Induktionssteg: Sedan visar man att P(k) är sant om P(i) är sant för alla i < k.

(Antagandet ”P(i) är sant för alla i < k” brukar kallas induktionsantagandet.)

Om vi lyckas visa båda dessa påståenden så är induktionsbeviset klart och vi kan vara säkra på att påståendet P(n) måste vara sant för alla n ≥ 0. Det kan man inse på följande sätt.

Att P(0) är sant bevisas i basfallet.
För att visa att P(1) är sant använder vi båda stegen i beviset. Basfallet säger att påståendet P(0) gäller. Induktionssteget säger, bland annat, att P(1) är sant om P(0) gäller. Dessa två påståenden tillsamman ger att P(1) är sant.
Nu kan vi upprepa samma argument för att visa P(2). Vi vet redan att P(0) och P(1) är sanna och kan därmed använda induktionssteget för att visa P(2). För k = 2 säger nämligen induktionssteget att ”P(2) är sant om P(i) är sant för alla i < 2”.
Med samma argument kan vi visa P(3), P(4), P(5) och så vidare.

Påståendet P(n) gäller alltså för alla tal n ≥ 0.

Exempel 1: summa

Vi börjar med ett påstående P(n) från matematiken:

1 + 2 + 3 + ... + n = n(n + 1)/2.

Vi använder matematisk induktion för att bevisa P(n) för alla n ≥ 1. (Om man låter den tomma summan vara noll så gäller även P(0).)

Basfall Vi vill bevisa påståendet för alla tal n ≥ 1 och startar därför induktionen på 1 i stället för 0. När n = 1 blir vänsterledet 1 och högerledet blir 1(1 + 1)/2 = 1. Påståendet P(1) är alltså sant.

Induktionssteg Vi ska visa att P(k) är sant om P(i) är sant för alla i < k. Vilket i detta fall betyder att vi antar (induktionsantagande) att

1 + 2 + ... + i = i(i + 1)/2 för alla i < k

och skall bevisa att

1 + 2 + ... + k = k(k + 1)/2.

Räkningen ser ut så här (vi använder induktionsantagandet för att räkna ut delsumman 1 + 2 + ... + (k - 1).):

1 + 2 + ... + k = (1 + 2 + ... + (k - 1)) + k = [här används induktionsantagandet] = ((k - 1)(k - 1 + 1)/2) + k = (k - 1)k/2 + 2k/2 = (k² + k)/2 = k(k + 1)/2.

Vi har nu visat både basfallet och induktionssteget och med hjälp av matematisk induktion kan vi dra slutsasten att P(n) är sant för alla positiva heltal n.

Exempel 2: samma summa i Java

Matematisk induktion fungerar utmärkt för att visa påståenden om rekursiva funktioner. Det är i själva verket ett mycket effektivt tankemönster för att förstå hur rekursiva funktioner fungerar.

Här är en rekursiv metod i Java som beräknar samma summa som i exemplet ovan.

/**
 * Returnerar summan 1 + 2 + ... + n, där n >= 1.
 */
public long sum(int n) {
    if (n == 1)
	return 1;
    return n + sum(n-1);
}

Vi vill bevisa påståendet P(n):

metodanropet sum(n) returnerar värdet 1 + 2 + ... + n

med hjälp av matematisk induktion.

Basfall P(1) är sant eftersom metoden returnerar 1 när n = 1.

Induktionssteg Vi antar (induktionsantagande) att P(i) är sant för alla i < k, dvs att metodanropet sum(i) returnerar 1 + 2 + ... + i när i < k, och ska försöka bevisa P(k).

Om k ≥ 2 så returnerar metodanropet sum(k) värdet k + sum(k-1). Men vi vet, enligt induktionsantagandet, att metodanropet sum(k-1) returnerar 1 + 2 + ... + (k-1). Därför kommer sum(k) att returnera

k + (1 + 2 + ... + (k-1)) = 1 + 2 + ... + k.

Med hjälp av matematisk induktion har vi nu bevisat att metodanropet sum(n) returnerar värdet 1 + 2 + ... + n när 1 ≤ n ≤ Integer.MAX_VALUE.

Exempel 3: binärsökning

Binärsökning har kallats ”den enklaste algoritm som ingen lyckas implementera korrekt”. Det verkar stämma; innan jag gav upp och skrev egen kod så hittade jag tio felaktiga Java-implementationer på nätet. Här kommer det att behövas både testkod och ett korrekthetsbevis!

private static final int NOT_FOUND = -1;

/**
 * Returns index of the first occurence of key in the sorted
 * subarray v[first..last], or -1 if key is not found.
 * Precondition: first <= last.
 */
private int binSearch(int[] v, int first, int last, int key) {
    if (first == last) {
        return key == v[first] ? first : NOT_FOUND;
    }

    // subarray with more than one element
    int mid = first + (last - first)/2;
    if (key <= v[mid]) {
        return binSearch(v, first, mid, key);
    } else {
        return binSearch(v, mid + 1, last, key);
    }
}

Den fullständiga implementationen med tillhörande testkod finns i filen BS.java.

Tänk gärna igenom koden och fundera på varför testen är key <= v[mid] och inte key < v[mid], och varför mid räknas ut på ett lite omständligt sätt. Kan man göra ändringar så att koden fungerar även om man byter ut key <= v[mid] mot key < v[mid]? Vilka fel tror du är typiska i trasiga implementationer av binärsökning?

Bevis

Påståendet P(n) som vi vill bevisa är

För en icke-tom sorterad subvektor v[first..last] av längd n = last - first + 1 så kommer metoden binSearch att returnera index för den första förekomsten av nyckeln key i subvektorn eller -1 om nyckeln saknas.

Basfall (n = 1) Om delvektorn har längd 1 så returneras rätt svar i den första if-satsen.

Induktionssteg Vi antar att påståendet P(i) är sant för alla i < k, dvs att metoden returnerar rätt svar om subvektorn innehåller färre än k element.

Vårt jobb är att bevisa påståendet P(k). Vi har redan visat P(1) så vi kan anta att k ≥ 2, vilket innebär att first < last. I detta fall kommer programmet att exekvera satsen

int mid = first + (last - first)/2;

Ett noggrannt studium av denna sats övertygar oss om att first ≤ mid < last. (Observera speciellt att satsen mid = (first + last)/2 inte hade fungerat eftersom summan kan spilla över så att resultatet blir fel.)

Vi skiljer nu på två fall. Om key ≤ v[mid] så vet vi att det sökta indexet endast kan finnas i subvektorn v[first..mid]. Eftersom antalet element i denna subvektor är mindre än k och minst ett så säger induktionsantagandet att anropet binSearch(v, first, mid, key) kommer att returnera rätt svar.

I det andra fallet gäller att key > v[mid] och det sökta indexet kan därför endast finnas i subvektorn v[mid+1..last]. Eftersom antalet element i denna subvektor är mindre än k och minst ett så säger induktionsantagandet att anropet binSearch(v, mid + 1, last, key) returnerar rätt svar.

Med hjälp av matematisk induktion har vi alltså bevisat att metoden binSearch uppfyller sin specifikation när 1 ≤ n ≤ Integer.MAX_VALUE.