rekursja

Witaj Amigo. Dziś Bilaabo opowie Ci, czym jest rekurencja.

Jak wiesz, w Javie niektóre metody wywołują inne metody. Jednocześnie w momencie wywołania metody przekazywane są do niej określone wartości argumentów, a podczas jej działania zmienne lokalne metody przyjmują określone wartości.

- Tak.

„A jak wiesz, zmienne wewnętrzne różnych metod są od siebie niezależne.

- Tak.

„Teraz wyobraź sobie sytuację, w której metoda może wywoływać samą siebie. To właśnie nazywa się rekurencją. Przykład:

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!

- Szczerze mówiąc, widzę, że metoda w kodzie wywołuje się sama, ale nie rozumiem, co dokładnie się dzieje, kiedy to się dzieje.

- Tak, mniej więcej tak samo, jak w przypadku wywołania innej metody.

- Nie, pytam, co się dzieje ze zmiennymi? Z ich znaczeniem? A jak wychodzimy z metody? A może wychodzimy wszyscy naraz?

- Bóg. Tak, wszystko jest dużo łatwiejsze. Wyobraź sobie, że metoda, która wywołuje samą siebie, była wielokrotnie propagowana. Wtedy będzie podobna sytuacja:

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

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

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!

Te. za każdym razem, gdy wywoływana jest metoda (nawet sama), tworzone są nowe zmienne do przechowywania danych dla tej metody. Nie ma wspólnych zmiennych.

Przy każdym wywołaniu w pamięci pojawia się kolejna kopia argumentów metody, ale z nowymi wartościami. Wracając do starej metody, używane są tam jej zmienne. Te. podczas rekurencji  w rzeczywistości wywołujemy inną metodę, ale z tym samym kodem, co nasz!

- Jasne. A jak działa wyjście z tych metod? Czy mogę prosić o przykład?

- OK. Jeden przykład jest wart tysiąca słów. Oto przykład dla Ciebie:

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. Niby zrozumiałe. Dlaczego potrzebujesz rekurencji?

- Istnieje wiele zadań podzielonych na osobne podzadania, które są identyczne z pierwotnym zadaniem. Na przykład musisz przejść przez wszystkie elementy drzewa XML. Każdy element może mieć kilka elementów podrzędnych i mają one swoje własne.

Lub musisz wyświetlić listę plików znajdujących się w katalogu i wszystkich jego podkatalogach. Następnie piszesz metodę, która wyświetla pliki z bieżącego katalogu, a następnie wywołujesz ją, aby uzyskać pliki ze wszystkich podkatalogów, ale z innym parametrem - podkatalogiem.

Przykład:

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

Linia 8 - pobierz listę wszystkich plików (i katalogów) w katalogu dir.

Linie 10-11 - jeśli plik jest faktycznie katalogiem, to aby wyświetlić jego pliki, ponownie wywołujemy  printAllFiles , ale z innym parametrem - podkatalogiem.

Linia 13 - wyświetl nazwę bieżącego pliku.

- OK. Niby zrozumiałe. Dzięki Bilabo.