Perché la ricorsione infinita non ha colpito un'eccezione di overflow dello stack in F #?

Question

So che questo è un po 'il contrario del problema che le persone stanno avendo quando fanno domande su un problema di overflow dello stack, ma se creo una funzione e la chiamo come segue, non ricevo mai errori e l'applicazione macina semplicemente un core della mia CPU fino a quando ho forzare lo spegnimento è:

let rec recursionTest x = 
    recursionTest x 

recursionTest 1 

Certo che posso cambiare questo in modo che in realtà fa qualcosa di simile:

let rec recursionTest (x: uint64) = 
    recursionTest (x + 1UL) 

recursionTest 0UL 

in questo modo posso ogni tanto mettere un punto di interruzione nel mio codice e vedere il valore di x sta salendo piuttosto rapidamente, ma non si lamenta ancora. A F # non interessa la ricorsione infinita?

Answer 1

La vostra funzione recursionTest è ricorsiva di coda, il che significa che tutte le chiamate ricorsive si verifica nella 'posizione di coda' vale a dire come l'ultima azione nella funzione. Ciò significa che il compilatore F # non ha bisogno di allocare un nuovo stack frame per le chiamate ricorsive, quindi non si verifica un overflow dello stack.

La ricorsione di coda è un caso specifico di tail call, la coda è chiamata a se stessa piuttosto che un'altra funzione.

Answer 2

Questo è un esempio di tail call optimization e pertanto il compilatore lo sta ottimizzando in un semplice ciclo. Vedere questo: http://blogs.msdn.com/b/fsharpteam/archive/2011/07/08/tail-calls-in-fsharp.aspx

provare qualcosa di simile:

let rec recursionTest x = 
    recursionTest x + recursionTest (x * 2) 

Answer 3

In generale, F # emette l'istruzione tailcall che quello .NET onori:

http://msdn.microsoft.com/en-us/library/system.reflection.emit.opcodes.tailcall(v=vs.95).aspx

In alcuni specifici casi semplici, come la vostra, F # riscrive programmi che utilizzano la ricorsione in programmi equivalenti utilizzando i cicli.