Quanto segue causerebbe un overflow dello stack per la grande 'n', e posso capire perché.Perché questo codice causa un overflow dello stack?
def factorial(n)
(n > 1) ? (return (n * factorial(n - 1))) : (return 1)
end
Perché anche la seguente causa trabocca?
def factorial(n, k)
(n > 1) ? (return factorial(n - 1, lambda {|v| return k.call(v * n)})) : (return k.call(1))
end
Il tuo secondo algoritmo crea una catena di procedure lambda n, ciascuna contenente un riferimento alla precedente. Non so esattamente cosa fa Ruby, ma in un linguaggio correttamente ricorsivo alla coda lo stack non traboccherebbe nel tuo secondo algoritmo, perché k.call nella lambda è anche in posizione di coda. Se, come suggerisce l'esperimento di Brian, Ruby non ha le opportune chiamate di coda, la catena n -lunga di chiamate nidificate al lambda eccederà lo stack quando viene richiamato il capo della catena, anche se Ruby è abbastanza intelligente da convertire la coda -recursive factorial chiamata in un ciclo (= ottimizzazione tail-call).
La seconda versione è ancora ricorsiva su fattoriale. Pensavo che Ruby non avesse fatto il TCO. Ma non fa saltare la pila finché non raggiunge i lambda. Non ho capito bene. (Tutti gli altri sono ancora più confusi, o non hanno letto la domanda. Sto svalutando gli altri in modo appropriato.) –
"Ma non fa esplodere la pila finché non raggiunge i lambda". - Ehm? Non capisco. –
Dato che il secondo esempio è ancora ricorsivo su 'fattoriale', mi aspettavo che trabocchi lo stack prima che raggiungesse mai il caso base di' k.call (1) '. Ma nel secondo codice di esempio sopra, le chiamate a 'factorial' non superano lo stack (anche per n molto grandi), che è un comportamento diverso rispetto al primo esempio. Il secondo esempio arriva a questo caso base e non trabocca finché non è avvenuto un sacco di 'k.call'. Senza TCO, non vedo come sia arrivato così lontano. –
Come nella prima funzione, le chiamate ricorsive possono finire per essere troppi per il sistema di gestire.
Nella maggior parte delle lingue, le chiamate di funzione passano allo stack di chiamate , che è in realtà solo lo stack. Chiamando una funzione in modo ricorsivo continua ad aggiungere allo stack delle chiamate. Alla fine si riempie lo stack e si ottiene un overflow dello stack. Questo è sempre un pericolo quando si esegue una funzione ricorsiva in cui il livello di ricorsione sarà profondo.
-1: cfr. "Il seguente sarebbe un overflow per la grande 'n', e posso capire perché" –
Per lo stesso motivo, il primo ha uno stack overflow ... Il callstack diventa troppo grande.
Overflow? o StackOverflow ?! –
-1, Appartiene a uservoice. –