Rekursiva metoder i Java: Underlättar och strukturerar större program

Den här artikeln kommer gå igenom och visa vad som menas med rekursion (engelska: recursion) i Java. Rekursion innebär att metoder anropa sig själv och är ett effektivt och elegant sätt att arbeta med metoder. Vi kommer se att rekursiva metoder underlättar och strukturerar vårt arbete i större program.

Vad är rekursion?

Rekursion är en process där en funktion/metod anropar sig själv, direkt eller indirekt, och den motsvarande funktionen kallas för en rekursiv funktion. Med hjälp av en rekursiv algoritm kan vissa problem lösas förhållandevis enkelt. Rekursion inom datavetenskap är en metod för att lösa ett problem där lösningen beror på lösningar till mindre instanser av samma problem. Rekursion löser då sådana problem genom att använda metoder som kallar sig själv från sin egen kod. Tillvägagångssättet kan tillämpas på många typer av problem, och rekursion är en av de centrala idéerna inom datavetenskap

En längre och mer utförlig förklaring om rekursiva algoritmer inom datavetenskap generellt finns hos KhanAcademy. I det här avsnittet kommer vi fokusera mer specifikt på hur vi kan använda rekursiva metoder i Java.

Vad är en rekursiv metod i Java?

En rekursiv metod i Java är en metod som definieras av att den har referenser till sig själv, det vill säga metoden anropar sig själv. Att använda sig av rekursiva metoder är en vanlig programmeringsteknik som kan skapa effektivare och mer sofistikerad kod. En rekursiv metod innehåller alltid ett basfall, även kallat det triviala fallet, som anger slutet på rekursionen och som därför inte anropar sig själv.

En rekursiv metod i Java är en metod som anropar sig själv.

Rekursiva metoder i Java

• är en referens till sig själv.
• innehåller alltid ett basfall.
• kan hantera direkta och indirekta anrop.
• vanlig teknik inom programmering och matematiken.

Hur fungerar en rekursiv metod i Java?

I Java så finns det tre centrala begrepp som är bra att känna till när man arbetar med rekursiva metoder:

• Basfall: En rekursiv metod måste alltid ha ett basfall. Detta är det triviala fallet som anger när rekursionen är klar. När basfallet är uppfyllt så returnerar metoden dess värde och processen fortsätter.
• Direkt anrop: En metod som anropar sig själv.
• Indirekt anrop: En metod som anropar en annan metod som i sin tur anropar den första metoden igen. Observera att indirekta anrop av denna anledning ofta är svåra att få någon översikt på.

Hur skapar man en rekursiv metod i Java?

Syntax för att skapa en rekursiv metod är helt enkelt att skapa en metod och sedan anropa den metoden inne i just samma metod. Om vi skriver det i kodeditorn så får vi

public static returtyp metodnamn () {

     // Kod som ska utföras 

     // Metoden anropar sig själv --> Rekursivt anrop
     metodnamn(); 
}

Exempel: Rekursiva metoder i Java

Enklast för att förstå hur en rekursiv metod är nog om vi tar två enklare exempel och kollar på det steg för steg. Det vi kommer att använda är ett direkt anrop, alltså en metod som anropar sig själv.

Exempel 1: Rekursiv metod som summerar heltal

Vi börjar med ett enklare exempel där vi ska använda en rekursiv metod. Det vi vill att vårt program ska göra är att:

• Vi ska nu skapa en rekursiv metod som summerar alla heltal mellan 1 och N.
• Först kollar vi basfallet, det vill säga om N är lika med ett. I detta fall finns det ingen anledning att anropa metoden igen, rekursionen behövs alltså inte i detta fall.
• Om N däremot är större än N, kommer metoden anropa sig själv tills dess att alla heltal är summerade.

private static int summa (int N) {
    // Hjälpvariabel
    int sum; 

    // Basfall
    if (N == 1) { 
        sum = 1;
    }
    else {
        // Metoden anropar sig själv --> Rekursivt anrop
        sum = N + summa(N - 1);  
    }

    //Returnera summan
    return sum; 
}

Ovanstående kod ger alltså följande fall

public static void main(String[] args) {
    System.out.println(summa(4));   //Skriv ut summan av alla heltal mellan 1 och 10
    System.out.println(summa(10));  //Skriv ut summan av alla heltal mellan 1 och 10
    System.out.println(summa(1));   //Basfallet
}

Som resulterar i utskriften,

10 
55 
1

Avslutningsvis, figur 1 nedan är en illustration hur funktionen fungerar då N = 3.

Skulle du vilja testa koden i exemplet ovan kan du göra det genom att klicka på knappen nedan.

Exempel 2: Rekursiv metod utan basfall

Låt oss ta ett till exempel, den här gången utan ett basfall. Med andra ord, vi har inget som indikerar när den rekursiva metoden är klar utan den kommer utföras oändligt många gånger och programmet kommer att krascha. Det är självklart inget vi rekommenderar, utan något vi tar upp för att visa vad som händer om man inte har ett basfall när man använder rekursiva metoder.

Vi skapar en metod vars enda uppgift är att skriva ut en text i konsolen. Metoden tar inte in några argument och returnerar inte heller något.

public class exempel {

    private static void printEx () {
        System.out.println("Metoden printEx skrivs ut");

        // Metoden anropar sig själv --> Rekursivt anrop
        printEx();
    }

    public static void main(String args[]) {   
        // Anropar metoden från main-metoden
        printEx();
    }
}

Om vi exekverar koden ovan så får vi resultatet,

Metoden printEx skrivs ut
Metoden printEx skrivs ut
Metoden printEx skrivs ut
Metoden printEx skrivs ut
Metoden printEx skrivs ut
... 
...
java.lang.StackOverflowError

Varför ska man använda rekursiva metoder i Java?

Ibland hjälper rekursion att utforma enklare och mer läsbar kod. Det är särskilt relevant för rekursiva datastrukturer (som träd) eller rekursiva algoritmer. Rekursion är ett förhållandevis strukturerat och smart sätt att göra kortare metoder och funktioner som är lätta att läsa. Noterbart är också att Java är inte mycket annorlunda när det gäller rekursion jämfört med andra programmeringsspårk, så om du lär dig grunderna vad rekursion innebär så kan du använda den logiken i andra programmeringsspråk också. Detta gäller självklart för många delar inom Java programmering, men är bra att påminna sig själv om ibland.

Vanliga misstag när man använder rekursiva metoder i Java

• Inte ha något basfall. Om du anropar en Metod utan basfall så kommer den upprepade gånger att anropa sig själv och kommer aldrig tillbaka från rekursionen
• Använda mycket minne i datorn. Om en funktion kallar sig rekursivt ett överdrivet antal gånger innan den återvänder, kan minnet som Java kräver för att hålla reda på rekursiva samtal vara väldigt stort och därav ta mycket kraft från datorn. Rekursion kan orsaka minnesproblem om dina iterationer är väldigt stora.
• Den rekursiva metoden minskar inte till ett mindre delproblem, så rekursionen konvergerar inte till en lösning.

Sammanfattning: Rekursiva metoder i Java

Rekursion är en process inom datavetenskap och matematik där en funktion/metod anropar sig själv, direkt eller indirekt, och den motsvarande funktionen kallas för en rekursiv funktion. Med andra ord, en rekursiv metod i Java är en metod som definieras av att den har referenser till sig själv, det vill säga metoden anropar sig själv. Det finns tre centrala begrepp när det kommer till rekursiva metoder i Java. Till att börja med, basfall, även kallat det triviala fallet, som anger slutet på rekursionen och som därför inte anropar sig själv. Vidare, ett direkt anrop, som är en metod som anropar sig själv. Slutligen, ett indirekt anrop, som betyder att en metod anropar en annan metod som i sin tur anropar den första metoden igen. Notera att indirekta anrop av denna anledning ofta är svåra att få någon översikt på.

För att läsa mer om rekursiva metoder i Java

Vidare, för att läsa mer om rekursiva metoder i Java så rekommenderar vi MIT Reading och Princeton Computer Science som båda har utförliga förklaringar och fler exempel.

Vanliga frågor och svar: Rekursiva metoder i Java