Nyckelord: rekursiva metoder, rekursion, basfall, direkt anrop, indirekt anrop
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.
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.
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
I Java så finns det tre centrala begrepp som är bra att känna till när man arbetar med rekursiva metoder:
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(); }
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.
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:
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.
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
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.
Lämna gärna feedback med hjälp av stjärnorna nedan och hjälp oss att fortsätta göra sidan bättre.
Vad tyckte du om sidan?
Lämna gärna feedback och hjälp oss göra sidan bättre
Feedback gör oss bättre!
Lämna gärna feedback om vad du tyckte om avsnittet!
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å.
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.
Det betyder att en metod eller funktion anropar sig själv. Det kan vara antingen ett direkt anrop, som betyder att metoden anropar sig själv, eller genom ett indirekt anrop som betyder att metoden anropar en annan metod som i sin tur anropar den första metoden igen.
För att skapa en rekursiv metod med ett direkt anrop så skapar man en metod som har en referens till sig själv. Med andra ord, man anropar den metod man har skapat inuti det kodblock som tillhör metoden.
Om rekursionen sker genom att metoden som anropar sig själv så är det ett direkt anrop. Däremot, om rekursionen sker genom att metoden anropar en annan metod som i sin tur anropar den första metoden igen, då är det ett indirekt anrop.
Vad tyckte du om sidan?
Lämna gärna feedback och hjälp oss göra sidan bättre
Feedback gör oss bättre!
Lämna gärna feedback om vad du tyckte om avsnittet!