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.

Dominoes

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.

(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.

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 = (k2 + 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.

/**
 * Returns the sum 1 + 2 + ... + n, where 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 n ≥ 1.

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!

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

    // Subarray with more than one element
    int mid = first + (last-first)/2; // to avoid overflow
    // Note: first <= mid < last
    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 Find.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 v.length 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 då kan spilla över så att resultatet blir negativt.)

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. Metoden fungerar därför eftersom en vektor i Java kan ha högst så många element.

Stefan Nilsson