Przepełnienie stosu spowodowane funkcją rekursywną

Question

Będąc początkującym programistą C++ i architekturą systemów komputerowych, wciąż uczę się podstaw języka C++. Wczoraj czytałem o funkcji rekurencyjnej, więc postanowiłem napisać własną rękę, oto co napisał: (bardzo podstawowy)

int returnZero(int anyNumber) { 
    if(anyNumber == 0) 
     return 0; 
    else { 
     anyNumber--; 
     return returnZero(anyNumber); 
    } 

}

I kiedy to zrobić: int Zero1 = returnZero (4793); powoduje to przepełnienie stosu, jednak jeśli przekażę wartość 4792 jako parametr, nie nastąpi przepełnienie.

Jakieś pomysły, dlaczego?

Answer 1

Po prostu osiągnąłeś limit połączeń stosu w swoim systemie, właśnie to się dzieje. Z jakiegoś powodu stos w twoim systemie jest mały, głębia 4793 wywołań funkcji jest raczej mała.

Answer 2

Za każdym razem, gdy wywołujesz funkcję, w tym rekursywnie, adres zwrotny i często argumenty są przekazywane do call stack. Stos jest skończony, więc jeśli rekursja jest zbyt głęboka, w końcu zabraknie miejsca na stosie.

Co mnie zaskakuje, to że 4793 wywołań na twoim komputerze ma przelać stos. To całkiem mały stos. Dla porównania, uruchamianie tego samego kodu na moim komputerze wymaga ~ 100x tyle połączeń, zanim program się zawiesi.

Rozmiar stosu można konfigurować. W systemie Unix polecenie to: ulimit -s.

Biorąc pod uwagę, że funkcja jest tail-recursive, niektóre kompilatory mogą być w stanie zoptymalizować wywołanie rekursywne przez przekształcenie go w skok. Niektóre kompilatory mogą wziąć przykład jeszcze dalej: gdy poprosił o maksymalnej optymalizacji, gcc 4.7.2 przemienia całą funkcję do:

int returnZero(int anyNumber) { 
    return 0; 
} 

Wymaga to dokładnie dwa instrukcje montażu:

_returnZero: 
     xorl %eax, %eax 
     ret 

Całkiem fajnie.

Answer 3

Twój stos ma ograniczony rozmiar, więc kiedy wykonujesz połączenia 4793, osiągasz limit, a 4792 po prostu wchodzi. Każde wywołanie funkcji użyje trochę miejsca na stosie do przechowywania domu i może argumentów.

Strona ta podaje example wygląd stosu podczas rekurencyjnego wywołania funkcji.

Answer 4

Zgaduję, że stos jest wystarczająco duży, aby zmieścić 4792 wpisy - dzisiaj. Jutro lub później ta liczba może być inna. Programowanie rekurencyjne może być niebezpieczne, a ten przykład pokazuje, dlaczego. Staramy się, aby rekurencja nie osiągnęła tak głębokich lub "złych" rzeczy.

Answer 5

Każda "nieograniczona" rekursja, czyli wywołania rekurencyjne, które nie są naturalnie ograniczone do małej (ish) liczby, będzie miała taki efekt. Dokładnie tam, gdzie granica idzie, zależy od systemu operacyjnego, środowiska, w którym funkcja jest wywoływana (kompilator, która funkcja wywołuje funkcję rekursywną, itp.).

Jeśli dodasz inną zmienną, powiedz int x[10]; do funkcji wywołującej funkcję rekursywną, liczba potrzebna do jej zawieszenia ulegnie zmianie (prawdopodobnie około 5).

Skompiluj go z innym kompilatorem (lub nawet różnymi ustawieniami kompilatora, na przykład włączoną optymalizacją) i prawdopodobnie prawdopodobnie zmieni się ponownie.

Answer 6

Korzystanie rekursji, można osiągnąć SuperDigit:

public class SuperDigit 
{ 
    static int sum = 0; 

    int main() 
    { 
     int n = 8596854; 
     cout<<getSum(n); 
    } 

    int getSum(int n){ 
     sum=0; 
     while (n > 0) { 
      int rem; 
      rem = n % 10; 
      sum = sum + rem; 
      n = n/10; 
      getSum(n); 
     } 
     return sum; 
    } 
}