Gdzie znaleźć rekurencję?

W dzisiejszych czasach programowanie w PHP polega zazwyczaj na ściągnięciu frameworka oraz zestawu dodatkowych bibliotek, a następnie powiedzeniu, gdzie kierować dane z bazy i jak je wyświetlić. Bynajmniej nie wynika to z lenistwa samych programistów, ponieważ większość Internetu to strony, które da się opisać zaledwie kilkoma prostymi zapytaniami SQL, a istnienie porządnych API jest zjawiskiem jak najbardziej pozytywnym. Jednak frameworki itd. nie tworzą się same, a na dokładkę ta mniejsza, lecz ciekawsza od strony projektowej część sieci może wymagać opracowania złożonych i dedykowanych systemów przetwarzania danych. Naturalnym środowiskiem występowania rekurencji są drzewa, a ta struktura danych znakomicie nadaje się do budowania układu dużych stron internetowych. W OPT występowanie rekurencji było w całości związane z drzewem XML, które kompilator generował z szablonu. Ogromna liczba zadań związanych z systemem plików operuje także na drzewie katalogowym i rekurencja pojawia się też tam. Do kategorii recursion-friendly zaliczyłbym także algorytmy grafowe, ale tych raczej przy kodowaniu w PHP się nie spotyka.

Podstępność rekurencji

Popatrzmy na zapis algorytmu przechodzenia drzewa metodą preorder. Polega ono na tym, że najpierw odwiedzamy aktualny węzeł, wykonując na nim operację, a później schodzimy kolejno do wszystkich dzieci i powtarzamy cały proces. W przypadku drzewa binarnego mamy:

 
 
function preorder($node)
{
   doSomething($node);
   if(!is_null($node -> left))
   {
      preorder($node -> left);
   }
   if(!is_null($node -> right))
   {
      preorder($node -> right);
   }
} // end preorder();
 

Algorytm jest niezwykle czytelny. Widzimy dokładnie, co jest wykonywane i w jakiej kolejności. Teraz małe zadanie: doimplementuj sobie klasę węzła takiego drzewa, zrób drzewo o głębokości 100 i spróbuj zapuścić na nim powyższą funkcję. Jeżeli tylko Twoja konfiguracja PHP nie była podkręcana, algorytm nie zakończy swojego działania z powodu zwyczajnego przepełnienia stosu - interpreter PHP posiada domyślny limit głębokości wywołań funkcji ustawiony na 64, którego zadaniem jest nie dopuścić do zbyt dużego zużycia zasobów. Prawda jest taka, że wiele algorytmów rekurencyjnych posiada duże zapotrzebowanie na pamięć. Zobaczmy, co tak dokładnie tu się dzieje. Wywołujemy preorder() na węźle głównym (korzeniu). Wykonuje się jakaś operacja, a my schodzimy najpierw do lewego syna. Wykonujemy na nim operację i schodzimy do jego lewego syna. W tym momencie PHP ma już otwarte trzy instancje naszej funkcji: dla rodzica, oraz dla dwóch jego lewych potomków. Każda z nich przechowuje własne informacje kontrolne oraz przestrzeń zmiennych. Gdy zejdziemy do głębokości 30, w pamięci rezydować będzie już 30 instancji. Załóżmy teraz, że nasz preorder jest dość złożony i potrzebuje dużo zmiennych wewnętrznych (sytuacja z OPT) - na każdym poziomie wszystkie one muszą być zapamiętane do czasu, gdy interpreter powróci z dzieci do instancji macierzystej. Nic dziwnego, że PHP broni się przed tym. Dodatkowe powody, dla których taki limit wprowadzono, to:

1. Zapobieganie przypadkowej rekurencji nieskończonej lub rekurencyjnemu include'owaniu plików.
2. Podobne limity istnieją także w normalnych językach programowania, lecz na poziomie sprzętowym. Głębokość rekurencji jest tam ograniczona wielkością stosu.

Usuwanie rekurencji

Każdy algorytm rekurencyjny da się zapisać bez rekurencji, lecz nie zawsze możemy wyeliminować do końca jej skutki. Najprościej jest z tzw. rekurencją ogonową, gdzie wynik działania aktualnej instancji funkcji staje się jednocześnie ostatecznym wynikiem działania całego algorytmu. Nie musimy wracać więc do instancji nadrzędnych, zatem są one potem już niepotrzebne. Można to w prosty sposób zasymulować przy pomocy pętli.

W pozostałych przypadkach tak czy inaczej potrzebujemy dodatkowej pamięci na przechowanie pewnych informacji. Dla naszego algorytmu preorder musimy zapamiętać, które węzły już odwiedziliśmy i do których dzieci przeskoczyliśmy. Doskonale nadaje się do tego nasz własny stos, wolny od limitu konfiguracyjnego. Zasada działania jest prosta:

1. Pętla wykonuje się, dopóki wskaźnik nie wskazuje na NULL lub stos nie jest pusty.
2. Jeśli da się iść w lewo, obsługujemy aktualny węzeł i przesuwamy wskaźnik na lewego syna.
3. Jeżeli nie da się iść w prawo, ściągamy element ze stosu do zmiennej tymczasowej. Jeśli da się iść w prawo, ustawiamy wskaźnik na prawego syna.

 
 
$node = $rootNode;
while(!is_null($node) || sizeof($stack) > 0) // 1
{
	if(!is_null($node)) // 2
	{
		doSomething($node); // obsluga elementu
		array_push($stack, $node);
		$node = $node -> left;
	}
	else // 3
	{
		$node = NULL;
		$tmp = array_pop($stack);
		if(!is_null($tmp -> right))
		{
			$node = $tmp -> right;
		}
	}
}

Warto zauważyć, jak w tym algorytmie sprawdzamy, których synów już odwiedziliśmy. Wykorzystany został do tego fakt istnienia (bądź nie) elementu na stosie. Na stosie może znaleźć się jedynie węzeł, któremu został do obsłużenia co najwyżej prawy syn. Co więcej, to działa.

Preorder jest jednym z algorytmów przeszukiwania w głąb - sięgamy zawsze tak głęboko, jak się da, a później wychodzimy. Jednak do przeszukiwań drzewa XML w OPT specjalnie nie robiło mi różnicy, czy najpierw odwiedzę dzieci węzła i przejdę do sąsiada, czy też najpierw sprawdzę sąsiada, a później ich wszystkie dzieci. Nazywamy to przeszukiwaniem wszerz i tutaj przydaje się kolejka:

 
$queue = array(0 => $rootNode);
do
{
  $node = array_shift($queue);
  doSomething($node);
  foreach($node as $child)
  {
    $queue[] = $child;
  }
}while(sizeof($queue) > 0);

Element znajdujący się w kolejce oczekuje na wykonanie. W pojedynczej iteracji pobieramy element z kolejki, obsługujemy go, a następnie wstawiamy wszystkie jego dzieci na koniec kolejki, dzięki czemu również zostaną obsłużone. Algorytm ten jest prostszy w implementacji, dlatego jeśli nie robi nam różnicy kolejność przeszukiwań, możemy z niego skorzystać.

Przypadki bardziej skomplikowane

Niestety, eliminacja rekurencji prawie zawsze prowadzi do pogorszenia czytelności kodu. Najgorsza sytuacja jest tam, gdzie użytkownik naszego cuda może samodzielnie programować poszczególne kroki i decydować, czy schodzić niżej. Natknąłem się na coś takiego w OPT - procesory instrukcji mogły decydować, czy i kiedy przetwarzać swoje dzieci (ew. mogły obrobić tylko część z nich). Całkowite pozbycie się rekurencji bez dostępu do niskopoziomowego programowania oznaczałoby straszliwe skomplikowanie API, dlatego zastosowałem rozwiązanie hybrydowe. Zauważyłem po prostu, że tylko niektóre instrukcje muszą w połowie swego wykonania znać status obróbki swoich dzieci, natomiast reszcie zwisa, kiedy faktycznie parser zajmie się ich potomstwem :). Te pierwsze dostają więc rekurencję na żądanie, a drugie dopinają się do aktualnie obowiązującej kolejki. Dzięki temu drzewo o głębokości nawet 40 może być teoretycznie wykonane przy użyciu 3-4 wywołań rekurencyjnych.

Rekurencja i bazy danych

Relacyjne bazy danych niezbyt nadają się do przetwarzania rekordów z zależnościami rekurencyjnymi. Próbowaliście napisać kiedyś forum z listą postów w formie drzewka? To jest właśnie to. Rekurencyjne wywoływanie zapytań to jeden z najgorszych pomysłów pod słońcem i należy unikać go, jak ognia (nawet z cache'owaniem). Sposoby są trzy:

1. Pobrać wszystko na chama i połączyć po stronie PHP
2. Zapisywać głębokość oraz położenie rekordu (pole order). Pobierając dane posortowane względem pola order, można na podstawie głębokości odbudować drzewo równolegle z jego pobieraniem. Operacje na takim drzewie powinny być stosunkowo łatwe do zaimplementowania.
3. Wykorzystać algorytm przechodzenia drzewa zmodyfikowaną metodą preorder (opisany w artykule "Drzewa w PHP i MySQL" do znalezienia na Zyxist.com). Jest on trudniejszy w implementacji, ale zapewnia dostęp do wielu ciekawych informacji o pojedynczym rekordzie (np. znajdowanie ścieżki do korzenia czy zliczanie potomków).

Podsumowanie

Rekurencja jest jednym z podstawowych zagadnień programistycznych. Jeżeli nie zamierzamy poprzestać na prostych stronkach, prędzej czy później na pewno ją spotkamy, a wtedy warto wiedzieć, jak oszukać interpreter i pozbyć się limitów.

PS. Nawiasem mówiąc wspomniany tekst "Drzewa w PHP i MySQL" zbiera całkiem sporo pochwał tak, że myślę nad jego przepisaniem od nowa z pokazaniem bardziej kompletnej implementacji włącznie.

Powrót

• Drzewa w PHP i MySQL

Na Zyxist.com panuje swoboda wyrażania opinii oraz krytyki pod dowolnym adresem. Jedyny warunek: musi być ona kulturalna i rzeczowa. Na chamstwo, prostactwo lub jawne obrażanie kogokolwiek nie ma tu miejsca i takie komentarze są bardzo szybko usuwane. Jeśli zamierzasz polemizować z treścią wpisu, wpierw uważnie ją przeczytaj.