Overflow dello stack causato dalla funzione ricorsiva

Question

Essendo un principiante dell'architettura di sistemi di programmazione e computer C++, sto ancora imparando le basi del C++. Ieri ho letto di funzione ricorsiva, così ho deciso di scrivere il mio, ecco quello che ho scritto: (molto semplici)

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

}

E quando faccio questo: int ZERO1 = returnZero (4793); provoca un overflow dello stack, tuttavia, se si passa il valore 4792 come parametro, non si verifica un overflow.

Qualche idea sul perché?

Answer 1

Hai appena raggiunto il limite di dimensioni dello stack di chiamate del tuo sistema, ecco cosa sta succedendo. Per qualche motivo lo stack nel tuo sistema è piccolo, una profondità di 4793 chiamate di funzione è piuttosto piccola.

Answer 2

Ogni volta che si chiama una funzione, incluso in modo ricorsivo, l'indirizzo di ritorno e spesso gli argomenti vengono inseriti nello call stack. La pila è finita, quindi se la ricorsione è troppo profonda finirà per esaurire lo spazio di stack.

Ciò che mi sorprende è che ci vogliono solo 4793 chiamate sulla vostra macchina per sovraccaricare lo stack. Questa è una pila piuttosto piccola. A titolo di confronto, l'esecuzione dello stesso codice sul mio computer richiede circa 100 volte il numero di chiamate prima che il programma si blocchi.

La dimensione dello stack è configurabile. Su Unix, il comando è ulimit -s.

Dato che la funzione è tail-recursive, alcuni compilatori potrebbero essere in grado di ottimizzare la chiamata ricorsiva allontanandola in un salto. Alcuni compilatori potrebbero prendere il tuo esempio ancora di più: quando gli viene chiesto per ottimizzazioni massimo, gcc 4.7.2 trasforma l'intera funzione in:

int returnZero(int anyNumber) { 
    return 0; 
} 

Questo richiede esattamente due istruzioni di montaggio:

_returnZero: 
     xorl %eax, %eax 
     ret 

Abbastanza pulito.

Answer 3

Lo stack è di dimensioni limitate e quindi quando si effettuano chiamate 4793 si sta raggiungendo il limite mentre 4792 è appena arrivato. Ogni chiamata di funzione userà un po 'di spazio nello stack per mantenere la casa e forse argomenti.

Questa pagina fornisce un example di come appare una pila durante una chiamata di funzione ricorsiva.

Answer 4

La mia ipotesi è che lo stack è esattamente grande abbastanza per contenere 4792 voci - oggi. Domani o il prossimo, quel numero potrebbe essere diverso. La programmazione ricorsiva può essere pericolosa e questo esempio non si spiega perché. Cerchiamo di non permettere alla ricorsione di ottenere che cose così profonde o "cattive" possano accadere.

Answer 5

Qualsiasi ricorsione "senza limiti", ovvero chiamate ricorsive che non sono naturalmente limitate a un numero piccolo (ish) avrà questo effetto. Esattamente dove il limite va dipende dal sistema operativo, dall'ambiente in cui viene chiamata la funzione (il compilatore, quale funzione chiama la funzione ricorsiva, ecc. Ecc.).

Se si aggiunge un'altra variabile, ad esempio int x[10]; alla funzione che chiama la funzione ricorsiva, il numero necessario per arrestarsi in modo anomalo cambierà (probabilmente circa 5 circa).

Compilalo con un compilatore diverso (o anche con impostazioni del compilatore diverse, ad esempio l'ottimizzazione attivata) e probabilmente cambierà nuovamente.

Answer 6

utilizzando la ricorsione, è possibile ottenere 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; 
    } 
}