Rekursion

"Hej, Amigo. I dag vil Bilaabo fortælle dig om rekursion."

Som du ved, kalder nogle metoder andre metoder i Java. Derudover, når en metode kaldes, overføres specifikke argumenter til den, men metodens lokale variabler tager visse værdier, mens den kører.

"Uh huh."

"Og som du ved, er forskellige metoders interne variabler uafhængige af hinanden."

"Uh huh."

"Så forestil dig den situation, hvor en metode kalder sig selv. Dette kaldes rekursion. 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 kalder sig selv i koden, men jeg forstår ærlig talt ikke, hvad der sker."

"Nå, omtrent det samme, der sker, når en anden metode kaldes."

"Nej, jeg spørger om, hvad der sker med variablerne? Med deres værdier? Og hvordan forlader vi metoden? Eller forlader vi alt på én gang?"

"Godhed elskværdig. Det hele er meget enklere. Forestil dig, at den metode, der kalder sig selv, er blevet mangedoblet mange gange. Så ville vi have den analoge situation:"

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 kaldes (selv af sig selv), oprettes nye variabler, der gemmer dataene for denne metode. Der er ingen delte variable."

"Ved hvert kald oprettes endnu en kopi af metodeargumenterne, med nye værdier, i hukommelsen. Når vi vender tilbage til den gamle metode, bruges dens variabler der. Med andre ord kalder vi under rekursion faktisk en anden metode, men med samme kode som vores! "

"Jeg kan se. Og hvordan virker det at forlade sådanne metoder? Måske et eksempel?"

"OK. Et eksempel siger mere end tusind ord. "Her er dit 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 har vi brug for rekursion?"

"Der er mange, mange opgaver, der kan opdeles i separate delopgaver, som er identiske med den oprindelige opgave. Du skal f.eks. gennemgå alle elementerne i et XML-træ. Hvert element kan have flere underordnede elementer, og de har deres egne børneelementer."

"Eller du skal vise listen over filer, der er i en mappe og alle dens undermapper. Så du skriver en metode, der viser filerne i den aktuelle mappe. Så for at få filerne til alle undermapper, kalder du din metode ved hjælp af en andet argument: en undermappe."

"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 mapper) i dir-mappen."

"Linje 10-11 – Hvis filen faktisk er en mappe, kalder vi printAllFiles igen, men denne gang med et andet argument: undermappen."

"Linje 13 – Vi viser navnet på den aktuelle fil."

"OK. Jeg tror, ​​jeg forstår. Tak, Bilaabo."