1750 Rekursion

Vad är rekursion?

Här följer en förklaring med hjälp av ett exempel från matematiken. Fakultet (eng. factorial) beräknas som i exemplet nedan.

3! = 3 * 2 * 1

public int factorial( int n ) {
  //basfall
  if ( n == 1 ) {
    return 1;
  }
  //rekrusivt anrop av metoden själv
  else {
    return n * factorial( n - 1 );
  }
}    

//nedan beskrivs ett metodanrop
factorial(3);

n = 3
return 3 * factorial(2)

n = 2 
return 2 * falctorial(1)

n = 1 
return 1

//Nu har factorial(1) fått värdet 1.
//(Vänd uppåt.)
//Sedan får factorial(2) värdet 2 * 1, d.v.s. 2
//Slutligen får factorial(3) värdet 3 * 2, d.v.s. 6

Uppgifter 1 - 5

Gör en ny klass Rekursion. Skriv metoderna i uppgift 1 - 5 i denna klass. Studera hur du löste uppgifterna i 704 for-slinga och serier. Nu ska uppgifterna lösas rekursivt istället.

Uppgift 1

Skriv en metod countDownFrom() som tar ett heltal som argument. Metodanropet countDownFrom(4); ger utskriften

4, 3, 2, 1, 0.

Uppgift 2

Metoden summa() tar en parameter som är ett heltal. Metoden returnerar summan av alla heltal som är mindre eller lika med det bifogade talet.

summa(4) //returnerar 10 d.v.s. (1 + 2 + 3 + 4)

summa(2) //blir 3 (1 + 2)

Uppgift 3

Metoden summaKvadrat()

summaKvadrat(n) = 1 * 1 + 2 * 2 + 3 * 3 + ... + n * n

//exempel
summaKvadrat(2) //blir 5 (1 * 1 + 2 * 2)

Uppgift 4

Metoden summaUdda() beräknar summan av alla tal som är udda och positiva och som är mindre eller lika med det tal som parametern anger.

summaUdda(n) = 1 + 3 + 5 + ... + n, om n är udda

//exempel
summaUdda(5) //blir 9
summaUdda(6) //blir också 9

Uppgift 5

Metoden summaJämna() beräknar summan av alla jämna tal som är mindre eller lika med n, där n är en heltalsparameter.

summaJämna(n) = 2 + 4 + 6 + 8 + ... + n, om n är jämnt

//exempel
summaJämna(8) //blir 20

Uppgift 6 - NY

Metoden jämntTalNummer() tar en parameter som anger vilket tal i nedanstående serie som ska returneras.

2, 4, 6, 8, 10, ...

Det första talet i serien är 2.

Nästa tal är två mer än det föregående.

Anropet jämntTalNummer(4) returnerar 8.

Uppgift 7 - NY

Skriv metoden uddaTalNummer(). Metoden tar en parameter som anger vilket tal i nedanstående serie som ska returneras.

1, 3, 5, 7, 9, 11,

Seriens första tal är 1.

Nästa tal är två mer än föregående tal.

Anropet uddaTalNummer(3) blir 5.

Uppgift 8 - NY

Metoden dubbeltTalNummer() returnerar det n:te talet i nedanstående serie.

1, 2, 4, 8, 16, 32, ...

Nästa tal är dubbelt så stort som föregående.

Anropet dubbletTalNummer(5) blir 16.

Uppgift 9 - NY

Metoden trippeltTalNummer() returnerar det n:te talet i nedanstående serie.

5, 15, 45, 135, 405, ...

Det första talet är 5.

Nästa tal är tre gånger så stort som det föregående.

Uppgift 10 - 12

Koden skrivs i klassen Numbers som använts vid sortering.

Uppgift 10 - NY

Skriv en metod printRekursivt() som skriver ut vektorn rekursivt. Metoden behöver ta en parameter.

Uppgift 11

Välj en sorteringsalgoritm och skriv den rekursivt, se nedan.

Skriv sorteringsalgoritmen, bubble sort, rekursivt. Det är nog den sorteringsalgoritm som är enklast att skriva rekursivt.

Eller skriv algoritmen för urvalssortering rekursivt.

Eller skriv en rekursiv metod för insättningssortering.

Uppgift 12

DET KOMMER KANSKE EN NY VARIANT

Skriv en metod binarySearch() som tar parametrarna:

• en sorterad vektor med heltal
• det sökta talet
• ett heltal minIndex, som är minsta index i subvektorn
• ett heltal maxIndex, som är största index i subvektorn

Metoden returnerar index för det sökta talet eller -1 om det sökta talet ej finns i vektorn.