0220 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 while - summor av serier. Nu ska uppgifterna lösas rekursivt istället.

Uppgift 1

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 2

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

4, 3, 2, 1, 0.

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

Metoden skrivUtJämnaTal() tar en parameter som anger hur många tal i nedanstående serie som ska skrivas ut.

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) skriver ut 2, 4, 6, 8

Uppgift 7

Skriv metoden skrivUtUddaTal(). Metoden tar en parameter som anger hur många udda tal som ska skrivas ut.

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) skriver ut 1, 3, 5

Uppgift 8

Metoden dubbeltTalSumma() returnerar summan av de n första talen i nedanstående serie.

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

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

Anropet dubbletTalSumma(5) returnerar 31 (1 + 2 + 4 + 8 + 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.