Problemy z rekurencją
Problemy związane z rekurencją
Programy wykorzystujące rekurencję wymagają użycia dużej ilości pamięci. Dla każdego wywołania funkcji (w tym rekurencyjnego) program musi umieścić w pamięci adres powrotu, wartości zmiennych lokalnych, jak również wartości argumentów wywoływanej funkcji. Dane te są niezbędne do odtworzenia stanu przed wywołaniem, w momencie zakończenia danej funkcji. Może to spowodować przepełnienie pamięci. Informacje te zapisywane są w wyznaczonym miejscu pamięci, które zwiemy stosem.
Rozwiązywanie niektórych problemów metodą rekurencyjną może także znacząco zwiększyć złożoność czasową algorytmu. W takiej sytuacji wskazane jest użycie wersji iteracyjnej rozwiązania problemu.
Aby zobrazować problem przepełnienia stosu, posłużmy się przykładem. Uruchomienie funkcji rekurencja(n), zdefiniowanej na początku tego e‑materiału, spowoduje uruchomienie drzewa rekurencyjnego o wysokości n. Oznacza to, że aby obliczyć wartość funkcji rekurencja(n), potrzebujemy na stosie obszaru o wielkości , gdzie jest pewnym współczynnikiem stanowiącym średnią ilości pamięci zajmowanej na stosie przy każdym kolejnym wywołaniu funkcji.
Miejsce na stosie zajmowane przez funkcję rekurencyjną zależy od liczby wywołań rekurencyjnych i ilości danych przechowywanych na stosie przez każde wywołanie.
W przypadku funkcji rekurencja(n), która wywołuje samą siebie dwukrotnie z argumentami (n - 1) i (n - 2), na stosie trzeba przechować dwa argumenty (typu int) oraz wartość zwracaną przez każde z dwóch wywołań. Ponieważ typ int zwykle zajmuje 4 bajty, to każde wywołanie funkcji rek zajmuje na stosie około 12 bajtów (2 x 4 bajty na argumenty i 4 bajty na wartość zwracaną).Dla przykładu, dla n = 5 funkcja rekurencja wykona 15 wywołań rekurencyjnych, a więc zajmie na stosie około 180 bajtów (15 x 12 bajtów). Jednak w przypadku większych wartości n ilość danych na stosie będzie znacznie większa, co może prowadzić do przepełnienia stosu.
Niech wynosi 16 bajtów. Wówczas przy zakładanej wielkości stosu maksymalna wartość , dla której możemy wywołać funkcję rekurencja(n) bez błędu przepełnienia stosu, wynosi:
W rzeczywistości program może zakończyć się dużo wcześniej. Np. interpreter języka Python domyślnie ogranicza liczbę wywołań rekurencyjnych do 1000. W języku C++ nie ma takiego ograniczenia.
Złożoność obliczeniowa tej funkcji wynosi O(n), ponieważ funkcja wywołuje samą siebie n razy, a każde wywołanie wykonuje stałą liczbę operacji (jedno dodawanie i jeden warunek).
Złożoność pamięciowa jest również O(n), ponieważ dla każdego wywołania funkcji rezerwowany jest nowy stos o stałym rozmiarze (w tym przypadku 4 bajty) na wartości zwracane przez wywołania rekurencyjne oraz zmienne lokalne. Zatem całkowita ilość pamięci potrzebna na utworzenie wszystkich stosów wynosi O(n * 4) = O(n).