Rekursjon

"Hei, Amigo. I dag vil Bilaabo fortelle deg om rekursjon."

Som du vet, i Java kaller noen metoder andre metoder. I tillegg, når en metode kalles, sendes spesifikke argumenter til den, men metodens lokale variabler tar visse verdier mens den kjører.

"Eh-he."

"Og som du vet, er forskjellige metoders interne variabler uavhengige av hverandre."

"Eh-he."

"Så forestill deg situasjonen der en metode kaller seg selv. Dette kalles rekursjon. For eksempel:"

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!

"Jeg kan se at metoden kaller seg selv i koden, men jeg forstår ærlig talt ikke hva som skjer."

"Vel, omtrent det samme som skjer når en annen metode kalles."

"Nei, jeg spør om hva som skjer med variablene? Med deres verdier? Og hvordan går vi ut av metoden? Eller går vi ut av alt på en gang?"

"Godhet nådig. Det hele er mye enklere. Tenk deg at metoden som kaller seg har blitt multiplisert mange ganger. Da ville vi ha den analoge situasjonen:"

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 andre ord, hver gang en metode kalles (selv av seg selv), opprettes nye variabler som lagrer dataene for denne metoden. Det er ingen delte variabler."

"Med hvert kall blir det opprettet en annen kopi av metodeargumentene, med nye verdier, i minnet. Når vi går tilbake til den gamle metoden, brukes variablene der. Med andre ord, under rekursjon kaller vi faktisk en annen metode, men med samme kode som vår! "

"Jeg skjønner. Og hvordan fungerer det å avslutte slike metoder? Kanskje et eksempel?"

"OK. Et eksempel sier mer enn tusen ord. "Her er ditt eksempel:"

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. Jeg tror jeg forstår. Hvorfor trenger vi rekursjon?"

"Det er mange, mange oppgaver som kan deles inn i separate deloppgaver som er identiske med den opprinnelige oppgaven. Du må for eksempel gå gjennom alle elementene i et XML-tre. Hvert element kan ha flere underordnede elementer, og de har sine egne barneelementer."

"Eller du må vise listen over filer som er i en katalog og alle dens underkataloger. Så du skriver en metode som viser filene til den gjeldende katalogen. Så for å få filene til alle underkatalogene, kaller du metoden din ved å bruke en annet argument: en underkatalog."

"For eksempel:"

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());
 }
}

"Linje 8 – Vi får listen over alle filer (og kataloger) i dir-katalogen."

"Linje 10-11 – Hvis filen faktisk er en katalog, kaller vi printAllFiles igjen, men denne gangen med et annet argument: underkatalogen."

"Linje 13 – Vi viser navnet på gjeldende fil."

"OK. Jeg tror jeg forstår. Takk, Bilaabo."