Wstęp
Obok wskaźników, rekurencja to drugi temat z najtrudniejszych do zrozumienia dla początkujących. W praktyce nie jest to trudne, jeśli się myśli o funkcjach we właściwy sposób. Jak powinieneś dobrze wiedzieć w tym punkcie kursu, funkcja to wydzielony fragment kodu, który można wywołać z różnych miejsc programu. Wołając
f() w
main() w gruncie rzeczy mówisz
"Wykonaj f, a potem wróć do main". Rekurencja to przypadek w którym funkcja jest wywoływana wewnątrz własnego ciała.
"Wykonaj f, a potem wróć do.. f..?".
Stos wywołań
Nie trzeba rekurencji, by program musiał pamiętać wiele wywołań naraz. Powiedzmy że mamy funkcje
f(),
g(),
h(), pierwsze dwie wywołują następną z tego ciągu. Będąc wewnątrz
h(), gdzieś musi być zapisane, że trzeba wrócić do
g(), a potem do
f(). Ponadto funkcja może być wywołana z wielu miejsc w programie, więc ta informacja nie może być też wbita do samej funkcji. Argumenty funkcji, adresy powrotów oraz zmienne lokalne funkcji są zapisane w lokacji pamięci nazywanej
stosem. Funkcja może być wywołana w dowolnym miejscu programu i po jej zakończeniu wykonywane będzie w tamtym miejscu wznowione. W szczególności, funkcja może być wywołana sama w sobie:
#include <iostream>
int silnia( int n )
{
if( n <= 1 )
return 1;
return n * silnia( n - 1 );
}
int main()
{
std::cout << silnia( 4 );
}
Tak można zaimplementować silnię, zgodnie z jej matematyczną rekurencyjną definicją:
Kolejne wywołania na stosie wyglądają w ten sposób:
Funkcja
silnia() nie liczy silni wprost, tylko
redukuje problem i
używa samej siebie do rozwiązania go. Redukcja problemu sprawia, że jest tu zawsze skończona ilość wywołań rekurencyjnych. W końcu dojdzie się do silni z 1, dla której określenie wyniku jest trywialne. Potem następuje odwijanie całej tej rekurencji, by złożyć szukany wynik, mając do dyspozycji wyniki mniejszych problemów. Dla zobrazowania tych dwóch faz, rozważ poniższą funkcję:
void test( int n )
{
std::cout << "Malejaco: " << n << '\n';
if( n > 0 )
test( n - 1 );
std::cout << "Rosnaco: " << n << '\n';
}
Malejaco: 5
Malejaco: 4
Malejaco: 3
Malejaco: 2
Malejaco: 1
Malejaco: 0
Rosnaco: 0
Rosnaco: 1
Rosnaco: 2
Rosnaco: 3
Rosnaco: 4
Rosnaco: 5
Ta funkcja wypisuje liczby od
n do zera, raz malejąco, drugi raz rosnąco. Sama w sobie, ta funkcja wypisuje tylko jedną wartość (
n), dwa razy. Dla
n > 0 używa samej siebie do wypisania tego samego dla mniejszego
n. Dopóki
n >= 0 następują kolejne wywołania rekurencyjne, wypisując liczby malejąco. Potem warunek przestaje być spełniony i zamiast wchodzić w głębszą rekurencję, funkcje kontynuują swoje działanie i wypisują swoje liczby jeszcze raz. Teraz w przeciwnej kolejności.
Wiele wywołań rekurencyjnych
Przykład silni łatwo przerobić na pętlę, bo jest tylko jedno wywołanie rekurencyjne i to na samym końcu funkcji. Rozważmy przykład, w którym funkcja redukuje rozwiązywany problem na więcej niż jeden podproblem. Tu klasyczny przykład to obliczanie
n-tego elementu ciągu Fibonacciego
#include <iostream>
unsigned fib( unsigned n )
{
if( n == 0 ) return 0;
if( n <= 2 ) return 1;
return fib( n - 1 ) + fib( n - 2 );
}
int main()
{
std::cout << fib( 6 );
}
Lub dokładniej: klasyczny przykład jak tego nie robić - ale do tego jeszcze wrócimy. Aby obliczyć element
n musimy znać elementy
n-1 i
n-2, więc rekurencyjnie je obliczamy.
n jest mniejsze wiec redukujemy problem - jakoś dążymy do rozwiązania. Ze szczególnym naciskiem na
jakoś.
Ta funkcja daje poprawny wynik, ale jak widać, sporo obliczeń na identycznych danych jest wykonywanych wielokrotnie. Wyobraź sobie tylko, co by było dla
fib(100).. Na pewno niepoprawny wynik, bo przekroczy zakres
unsigned. Do tego nikt z nas nie dożyje uzyskania tego wyniku. Mój komputer liczy
fib(40) w około sekundę, więc
fib(100) będzie trwać ~30 miliardów lat na takiej maszynie. Obliczenie wartości ciągu fibonacciego to bynajmniej nie jest jakiś trudny problem, po prostu taka implementacja nie jest nic warta
;)Ograniczenia i pułapki
Rekurencja ma jedną dużą zaletę: jeśli mamy skomplikowany problem, który łatwo się redukuje i nie trzeba wielu takich redukcji, wyrażenie go rekurencją jest łatwe i czytelne. Redukcji nie może być zbyt wiele, bo jest limit, ile można wykonać wywołań rekurencyjnych. Jest ograniczona ilość miejsca na stosie, więc da się go przepełnić i wywołać błąd krytyczny aplikacji. Większe i cięższe argumenty i zmienne lokalne funkcji przyspieszają ten proces, bo zwiększają ilość miejsca, które jest zajmowane na stosie z każdym wywołaniem.
Inną pułapką jest to, że łatwo napisać coś o paskudnej złożoności obliczeniowej, tak jak ta implementacja Fibonacciego. Wygląda niewinnie, jest wręcz skopiowana z matematycznej definicji, a jednak jest to prawdopodobnie najgorsza możliwa implementacja.
Dodatek
Przykład z liczbami malejącymi i rosnącymi opisany w jeszcze inny sposób: