Rekursion

"Hej Amigo. Idag ska Bilaabo berätta om rekursion."

Som du vet, i Java kallar vissa metoder andra metoder. Dessutom, när en metod anropas skickas specifika argument till den, men metodens lokala variabler tar vissa värden medan den körs.

"Äh-ha."

"Och som ni vet är olika metoders interna variabler oberoende av varandra."

"Äh-ha."

"Så föreställ dig situationen där en metod kallar sig själv. Detta kallas rekursion. Till exempel:"

public static void main(String[] args)
{
 countDown(10);
}

public static void countDown(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown(x - 1);
 }
}

10
9
8
7
6
5
4
3
2
1
Boom!

"Jag kan se att metoden kallar sig i koden, men jag förstår ärligt talat inte vad som händer."

"Tja, ungefär samma sak som händer när en annan metod kallas."

"Nej, jag frågar om vad som händer med variablerna? Med deras värden? Och hur går vi ur metoden? Eller går vi ur allt på en gång?"

"Godhet nådig. Det hela är mycket enklare. Föreställ dig att metoden som kallar sig har mångdubblats många gånger. Då skulle vi ha den analoga situationen:"

public static void main(String[] args)
{
 countDown(10);
}

public static void countDown(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown(x - 1);
 }
}

public static void main(String[] args)
{
 countDown1(10);
}

public static void countDown1(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown2(x - 1);
 }
}
public static void countDown2(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown3(x - 1);
 }
}
public static void countDown3(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown4(x - 1);
 }
}

public static void countDown4(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  countDown5(x - 1);
 }
}

3
2
1
Boom!

3
2
1
Boom!

"Med andra ord, varje gång en metod anropas (även av sig själv), skapas nya variabler som lagrar data för denna metod. Det finns inga delade variabler."

"Med varje anrop skapas ytterligare en kopia av metodargumenten, med nya värden, i minnet. När vi återgår till den gamla metoden används dess variabler där. Med andra ord, under rekursion anropar vi faktiskt en annan metod, men med samma kod som vår! "

"Jag förstår. Och hur fungerar det att lämna sådana metoder? Kanske ett exempel?"

"OK. Ett exempel säger mer än tusen ord. "Här är ditt exempel:"

public static void main(String[] args)
{
 print(3);
}

public static void print(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  print(x - 1);
  System.out.println(x);
 }
}

public static void main(String[] args)
{
 print1(3);
}

public static void print1(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  print2(x - 1);
  System.out.println(x);
 }
}

public static void print2(int x)
{
 if (x <= 0)
  System.out.println("Boom!");
 else
 {
  System.out.println(x);
  print3(x - 1);
  System.out.println(x);
 }
}

…

3
2
1
Boom!
1
2
3

3
2
1
Boom!
1
2
3

"OK. Jag tror att jag förstår. Varför behöver vi rekursion?"

"Det finns många, många uppgifter som kan delas upp i separata deluppgifter som är identiska med den ursprungliga uppgiften. Till exempel måste du gå igenom alla element i ett XML-träd. Varje element kan ha flera underordnade element, och de har sina egna barnelement."

"Eller så måste du visa listan över filer som finns i en katalog och alla dess underkataloger. Så du skriver en metod som visar filerna i den aktuella katalogen. För att sedan hämta filerna för alla underkataloger, anropar du din metod med en annat argument: en underkatalog."

"Till exempel:"

public static void main(String[] args)
{
 printAllFiles(new File("c:/windows/"));
}

public static void printAllFiles(File dir)
{
 for (File file : dir.listFiles())
 {
  if (file.isDirectory())
   printAllFiles(file);
  else
   System.out.println(file.getAbsolutePath());
 }
}

"Rad 8 – Vi får listan över alla filer (och kataloger) i dir-katalogen."

"Rad 10-11 – Om filen faktiskt är en katalog, anropar vi printAllFiles igen, men den här gången med ett annat argument: underkatalogen."

"Rad 13 – Vi visar namnet på den aktuella filen."

"OK. Jag tror jag förstår. Tack, Bilaabo."