Jednym z ciekawszych sposobów rozwiązywania problemów w programowaniu jest korzystanie z rekurencji. Niestety w językach proceduralnych jest to obarczone dużym użyciem pamięci operacyjnej ze stosu, co z jednej strony jest wolne, z drugiej owa pamięć potrafi się dość często wyczerpać. Zazwyczaj więc zaleca się stosować algorytmy oparte na pętlach.
Ale czasami kompilator potrafi sobie z tym poradzić i obejść się bez stosu. Tak się zazwyczaj dzieje w przypadku zastosowania rekurencji ogonowej. Zasadniczo aby móc z niej skorzystać, ostatnim poleceniem w procedurze, czyli tym ogonkiem, musi być zwrócenie danych pobranych z wywołania rekurencyjnego. Dzięki temu kompilator nie musi zapamiętywać na stosie aktualnego stanu zmiennych lokalnych i nie musi generować kolejnego adresu powrotnego. Dzięki temu po kompilacji kod wygląda praktycznie jak zwykła pętla i działa tak samo sprawnie.
Poniżej dwie grafiki ilustrujące rekurencje, kolejno zwykłą i ogonową.
Osobiście uważam, że stosowanie rekurencji zapewnia czytelniejszy kod. Jednocześnie jednak zdaję sobie sprawę, że stosowanie konwencjonalnych pętli ułatwia zadanie kompilatorom. Niemniej, jeśli ktoś zdecyduje się na pierwsze rozwiązanie, wersja ogonowa może zapewnić większą wydajność bez ograniczania czytelności.
Aby sprawdzić w praktyce skuteczność mojej hipotezy, napisałem dwie proste procedury w C. Zdecydowałem się zaimplementować prosty generator liczb pseudolosowych, który może by się sprawdził jako substytut rzutu kostką.
uint_fast16_t my_rand_tail(uint_fast16_t seed, size_t i)
{
uint_fast32_t t, t1, t2;
if (i) {
t = seed;
t1 = t ^ (t >> 1);
t2 = (t ^ (t << 2)) + 0xf0000;
t = (t2 - t1) & 0xffff;
return my_rand_tail(t, --i);
} else {
return seed;
}
}
uint_fast16_t my_rand_not_tail(uint_fast16_t seed, size_t i)
{
uint_fast32_t t, t1, t2;
if (i) {
t = my_rand_not_tail(seed, --i);
t1 = t ^ (t >> 1);
t2 = (t ^ (t << 2)) + 0xf0000;
t = (t2 - t1) & 0xffff;
} else {
t = seed;
}
return t;
}
Jeśli chodzi o czytelność samego kodu, nie widzę różnicy. Jeśli zaś chodzi o wydajność, wersja ogonowa może być nawet dwa razy szybsza. Przetestowałem na dwóch różnych komputerach i używając dwóch ogólnodostępnych kompilatorów, z najwyższym standardowym poziomem optymalizacji (-O3). Poniżej wykres.
Oczywiście w rzeczywistym kodzie okazji na stosowanie rekurencji ogonowej jest dużo mniej. Większości algorytmów nie da się sprowadzić do tej postaci. Dużo czasu jest też tracone na wywołania obcych albo systemowych procedur. Ale jeśli ta drobna optymalizacja nie ogranicza czytelności kodu, nie ma powodu aby jej nie stosować.