Induktion och rekursiva funktionerFö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 induktionMatematisk 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.
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.
Exempel 1: summaVi 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 < koch 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 JavaMatematisk 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.
Vi vill bevisa påståendet P(n): metodanropet sum(n) returnerar värdet 1 + 2 + ... + nmed 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. (Eftersom Javas int-typ har begränsad noggrannhet så fungerar dock bara steg två i beviset så länge k + sum(k-1) är mindre än Integer.MAX_VALUE.) Exempel 3: binärsökningBinä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!
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? BevisPå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
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. Metoden fungerar därför eftersom en vektor i Java kan ha högst Integer.MAX_VALUE element. |