Quanto spazio consuma una ricorsione?

[Peternek]

Ciao a tutti! Vi chiedo per favore di aiutarmi con un dubbio. Sto leggendo un po' su internet ma non capisco bene quanto spazio consuma un algoritmo ricorsivo. Ad esempio ho appena fatto un algoritmo ricorsivo che mi da la dimensione della massima sottostringa palindrome di una parola che se date un'occhiata è tipo un forma tipo un albero di N^2 nodi "chiamate", ma la profondità delle foglie è N. Però so che ha uno stack interno.. insomma di solito esiste un modo per capire quanto spazio richiede una ricorsione?
(per chi volesse dare un'occhiata anche al codice:)

Codice: Seleziona tutto

int palindrome(char word[], int i, int j, int count)
{
   if(j-i==1)
   {
      if(word[i]==word[j])
         return count+2;
      return 0;
   }
   int dim = 0;
   if(word[j]==word[i])
      dim = count+2;
   int left = palindrome(word, i, j-1, dim);
   int right = palindrome(word, i+1, j, dim);
   if(left>right)
      return left;
   return right;
}


[GuidoB]

Ciao Peternek,

ho appena fatto un algoritmo [...]. Però so che ha uno stack interno..

Lo stack è del processo o del thread, non dell'algoritmo.

Lo spazio che richiede una chiamata ricorsiva dipende del compilatore, dalle dimensioni dei parametri che passi e da quelle delle variabili locali, dalle dimensioni dell'indirizzo di ritorno e da eventuali byte di allineamento:

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

A volte il chiamante riserva spazio sullo stack anche per il valore di ritorno della funzione, ma se questo è di un tipo che non occupa troppa memoria, generalmente viene ritornato in uno o più registri del processore.

Alcuni compilatori usano registri anche per passare i parametri che possono starci. Tuttavia in caso di successiva chiamata ricorsiva il chiamato dovrà comunque salvarli, quindi alla fine occuperanno spazio sullo stack. Lo stesso vale per le variabili locali.

Per sapere quanto occupa una chiamata ricorsiva della tua funzione sullo stack potresti stampare l'indirizzo di una qualsiasi delle variabili locali, per esempio:

Codice: Seleziona tutto

printf("0x%08X\n", &dim);

e vedere di quanto cambia tra una chiamata e la successiva. La differenza tra i due indirizzi è la dimensione occupata sullo stack da ogni singola chiamata ricorsiva.

Nel tuo caso, ipotizzando che l'indirizzo di ritorno e ogni parametro e variabile locale (compresi eventuali byte di allineamento) occupino 32 bit (cioè 4 byte), siccome hai 4 parametri, 3 variabili locali e 1 indirizzo di ritorno, stimo che ogni chiamata ricorsiva occupi 64 byte di stack. Comunque dipende anche dal compilatore e dalle ottimizzazioni che imposti.

Per sapere la memoria totale occupata da tutta la catena di chiamate ricorsive dovresti conoscere la profondità massima di ricorsione (nel caso più sfortunato).

Ci sono algoritmi (per esempio il quicksort) dove si possono inserire modifiche apposta per evitare che si diano i casi più sfortunati, in modo da garantire che la massima quantità di stack occupata sia proporzionale, per esempio, a e non a (dove è il numero di elementi da processare). Nel quicksort la garanzia si può ottenere con la scelta di eseguire sempre per prima la parte più corta (con ricorsioni meno profonde), in modo di non doverne mantenere il riferimento sullo stack quando si va ad eseguire la parte più lunga (con ricorsioni più profonde).

Ci sono anche algoritmi ricorsivi in cui si può sostituire la ricorsione con cicli (ad esempio il calcolo del fattoriale). Spesso si riconoscono perché hanno (o si può spostare) la chiamata ricorsiva all'inizio o alla fine della funzione.
Credo che anche la ricerca di una sottostringa palindroma si possa scrivere solo con cicli, senza ricorsione.
Negli altri casi si possono eliminare le chiamate ricorsive utilizzando internamente alla funzione uno stack, che però è solo un modo mascherato (magari più controllabile) di effettuare una ricorsione.

In applicazioni reali (non dimostrative) la ricorsione è da evitare il più possibile perché non permette al compilatore di sapere in tempo di compilazione la quantità di stack occupata da un processo. Questo obbliga a una gestione più complessa e aggiunge la possibilità che la memoria disponibile non sia sufficiente a terminare l'esecuzione, con conseguenze reali che possono essere catastrofiche. Infatti la ricorsione è una delle cose vietate dalle regole MISRA C, che si applicano in software di controllo veicolare e avionico.

[Peternek]

Intanto La ringrazio di cuore per la dettagliata spiegazione!
Ora mi è più chiaro come avviene fisicamente e a quanto pare dipende molto dai casi. Però non capisco se questi stack sono di più o ce ne è uno solo... E' che non conosco fisicamente cosa ci sia dietro ai codici perciò mi rimane ancora questo dubbio:

Per sapere la memoria totale occupata da tutta la catena di chiamate ricorsive dovresti conoscere la profondità massima di ricorsione (nel caso più sfortunato).

in modo da garantire che la massima quantità di stack occupata sia proporzionale, per esempio, a \log n e non a n (dove n è il numero di elementi da processare)

Mi rimane un dubbio su come cresce la memoria totale occupata. Se fosse possibile dare diciamo una stima sulla sua crescita sarebbe più incontrata una crescita che dipende dalla profondità della chiamata quindi "altezza massima dell'albero" o dagli "elementi da processare" o magari anche dal numero totale di nodi.
So che se la profondità ad esempio è e l'albero della chiamata è binario triangolare: i nodi sono . Lo stack crescerebbe come , o magari il numero degli elementi da processare che sono invece (nel caso palindrome)

[xyz]

Alcuni compilatori possono aiutare fornendo lo stazio occupato nello stack quando viene chiamata ogni singola funzione.

Il GNU GCC ad esempio ha l'opzione "-fstack-usage" per abilitare la scrittura di un file di supporto "file.su" con la descrizione dettagliata dello stazio occupato nello stack di ogni singola funzione. I dettagli nel manuale:

https://gcc.gnu.org/onlinedocs/gnat_ugn ... lysis.html

questa analisi viene fatta al tempo della compilazione, non al runtime.

Per una analisi al runtime esiste un modulo di Valgrind che si chiana Callgrind:

http://cs.swan.ac.uk/~csoliver/ok-sat-l ... anual.html

il quale permette di esaminare il numero di chiamate e il tempo di chiamata di ogni singola funzione.

Il numero di stack dipende dalla CPU e dal sistema operativo. Nei sistemi più semplici lo stack è uno solo ed è globale, nelle CPU più complesse si hanno più stack separati e indipendenti.

[GuidoB]

Però non capisco se questi stack sono di più o ce ne è uno solo...

Nel tuo caso devi considerare un solo stack, quello con cui gira il tuo processo. Se ci sono altri processi, o il processore ha vari stack fisici per eseguire più processi in parallelo o per questioni di protezione/sicurezza, non impattano sulla tua stima.

Mi rimane un dubbio su come cresce la memoria totale occupata. Se fosse possibile dare diciamo una stima sulla sua crescita sarebbe più incontrata una crescita che dipende dalla profondità della chiamata quindi "altezza massima dell'albero" o dagli "elementi da processare" o magari anche dal numero totale di nodi.

Non so se ho capito bene il tuo dubbio, ma provo a risponderti. Sono però cose che ho studiato tanto tempo fa, quindi prendi il tutto con riserva di controllare.
L'occupazione massima di stack di un albero di chiamate ricorsive è pari all'occupazione di stack di una chiamata moltiplicata per l'altezza dell'albero.
Se non c'è qualche modo per evitare il caso più sfortunato, bisogna considerare proprio quello (nel quicksort è quando l'albero è sbilanciato tutto a destra o tutto a sinistra).
L'altezza dell'albero completamente sbilanciato è pari al numero di nodi.

Non sono entrato nei dettagli del tuo algoritmo, ma guardando il codice ti direi che presenta una profondità massima di ricorsione pari al numero di elementi dell'array word[] meno uno. L'occupazione di stack è quindi .

[Peternek]

Perfetto anche questo dubbio risolto! Grazie mille a tutti!