Cause di overflow dello stack in funzioni ricorsive

Question

In this video attorno al limite dei 28 minuti, Brian Harvey è stato chiesto da uno studente se dovessimo sempre utilizzare un processo iterativo su un processo ricorsivo durante la scrittura dei programmi. Ha risposto di no, perché

I tuoi programmi non scenderanno nei limiti di spazio. E in termini di localizzazione di ciò che è in memoria, devi avere un controllo molto maggiore rispetto a quello che fai nel modo in cui il programma viene interpretato per influenzarlo davvero.

Poiché non si tratta di un corso di schema, ho pensato che stia parlando in generale dei linguaggi di programmazione. E quando ha detto "I tuoi programmi non incorreranno in limiti di spazio.", Sta ignorando gli overflow dello stack? Sono confuso dalla sua risposta perché non ha uno stack overflow significa che hai già esaurito lo spazio con le chiamate di funzione? Non capisco nulla dalla parte "in termini di località". Gli overflow dello stack possono capitare a schema, java e altre lingue. Ho corretto o sto fraintendendo la sua affermazione?

Answer 1

Il video a cui ti riferisci è una lezione di informatica L'informatica è in gran parte teorica e affronta molti dettagli dell'informatica che non sono rilevanti nella praticità: in questo caso, come dice all'inizio della lezione, i computer di oggi sono grandi e abbastanza veloci da rendere raramente un problema di prestazioni

---

La località di memoria non è correlata a StackOverflowException s, in nessuna lingua. In realtà, la localizzazione della memoria si riferisce alla SRAM (RAM statica), che contiene una cache di dati adiacenti introdotti ogni volta che il bus recupera i dati dalla memoria (può essere il disco o la RAM). Prendere i dati da questa cache è più veloce che ottenerlo dalla memoria, quindi un programma funzionerà più velocemente se tutti i dati necessari per diverse operazioni consecutive sono all'interno della cache.

---

Ora è tutto molto di basso livello. Dietro la maggior parte (se non tutti) i linguaggi moderni, come Java, c'è un compilatore che lavora per fare numerose ottimizzazioni a basso livello. Ciò significa, in primo luogo, che c'è poco che puoi fare per ottimizzare il tuo codice a un livello basso, specialmente senza interferire con le ottimizzazioni del compilatore. In secondo luogo, (come dice lui subito dopo il segmento a cui ti riferisci) a meno che tu non stia facendo un gioco ad alta intensità di risorse, non vale la pena dedicarti alle prestazioni (a meno che tu non abbia problemi di prestazioni evidenti, ma è più probabile un'indicazione di altri problemi nel codice).

Answer 2

Oggigiorno, con il nostro enorme sovraccarico di stack di memoria, spesso è il segno di una ricorsione infinita, proprio come con un programma iterativo senza interruzioni è il segno di un ciclo infinito.

Quindi sì, ha ragione.

Answer 3

La procedura ricorsiva causerà un overflow dello stack? Dipende dal tipo di procedura ricorsiva che hai progettato, a seconda del problema, la maggior parte delle ingenue ricusioni possono essere convertite in chiamate di coda (in linguaggio TCO ottimizzato chiamata coda), che consente a una ricorsione di essere eseguita nello spazio di memoria costante senza usare la mutazione o altre cose di stato.

Nello schema, un processo iterativo:

(let ((i 0) 
     (max 10)) 
    (let loop() 
    (cond ((< i max) 
      (printf "~A~N" i) 
      (set! i (+ i 1)) 
      (loop)) 
      (else i)))) 

Questa procedura utilizza memoria costante, che è uguale allo spazio necessario per memorizzare la chiamata al ciclo sulla pila. questa procedura non è una funzione, usa la mutazione per iterare (è anche una ricorsione;) ma ..).

Nello schema, due ricorsioni:

(define (fact-1 n) 
    (cond ((eq? n 1) n) 
     (else (* n (fact-1 (- n 1)))))) 

(define (fact-2 n carry) 
    (cond ((eq? n 1) carry) 
     (else (fact-2 (- n 1) (* carry n))))) 

Fact-1 è una ricorsione normale, ed è molto funzionale, non v'è alcun cambiamento di stato, invece, l'uso della memoria cresce come nuove chiusure lessicali sono creato con ciascuna chiamata fact-1, esaurendo infine la pila. Cresce come

=>(fact-1 10) 
..(* 10 (fact-1 9)) 
..(* 10 (* 9 (fact-1 8))) 
..(* 10 (* 9 (* 8 (fact-1 7)))) 
..  ..... 
..(* 10 (... (* 2 1) ...)) 
..  ..... 
..(* 10 362880) 
=>3628800 

considerando Fact-2 è ricorsiva, ma in forma di coda, così invece di costruire stack, e comprimendo le chiamate allo scenario di base, il valore viene passato avanti e otteniamo questo:

=>(fact-2 10 1) 
..(fact-2 9 10) 
..(fact-2 8 90) 

..(fact-2 7 720) 
.. .......(fact-2 1 362880) 
=>3628800 

Che equivale a rendere fact-1 in un processo di interazione, ma senza alcuna mutazione, in quanto i valori vengono inoltrati anziché essere assegnati. Si noti che ogni chiamata produce ancora una nuova chiusura lessicale, ma poiché la funzione non ritorna al chiamante originale, ma alla posizione dello stack dei chiamanti originali, il compilatore può scartare le chiusure precedenti invece di averle annidate l'una nell'altra, re-binding le variabili a ciascun livello di ricorsione.

Quindi, dove dovrei usare la ricorsione o l'iterazione Ciò dipende interamente dal processo da progettare e dal linguaggio utilizzato. Se la tua lingua non supporta TCO, dovrai utilizzare solo ricursioni superficiali e scrivere in loop procedure (ricorsive o iterative) in modo statico. Se si dispone di TCO, potrebbe essere preferibile utilizzare la ricorsione, le chiamate di coda o le informazioni sullo stato o una combinazione di esse. Non tutte le procedure ricorsive possono essere scritte in coda, e non tutti i processi iterativi possono essere scritti come ricorsione. Se sei preoccupato per l'utilizzo della memoria e desideri ricchezioni profonde, devi utilizzare le Tail-calls.

NOTA: Alcuni di voi avranno notato, ma la prima procedura è in realtà una chiamata coda troppo, ma l'esempio illustra ancora il punto di un'iterazione normale fare stateful! cose e in esecuzione nella memoria massima costante indipendentemente da tutti gli input validi.