Funzioni ricorsive, overflow dello stack e Y-Combinators

Question

Ho una funzione ricorsiva (in C #) che devo chiamare circa 800 milioni di volte;questo ovviamente si tradurrebbe normalmente in un overflow dello stack dopo circa la 900a chiamata.L'ho distribuito a più cicli, ma il modello ricorsivo è molto più semplice e pulito da mantenere.

Sto cercando di implementare la funzione ricorsiva usando un combinatore y, da quello che ho letto e visto, che dovrebbe risolvere il problema dell'overflow dello stack e correggere i loop multipli annidati.

Qualcuno ha esperienza nell'uso del combinatore y?Sarò ancora bloccato in uno stack overflow?

Prendiamo il semplice esempio di un fattoriale.Un fattoriale sulla maggior parte dei numeri maggiori di 5.000 provocherà un overflow dello stack.Se usassi correttamente un combinatore y in quello scenario, risolverebbe l'overflow dello stack?

Non sembra banale da implementare, quindi voglio confermarlo prima di spendere lo sforzo / le risorse di sviluppo per implementare e imparare il combinatore y.

Answer 1

No, l'uso del combinatore Y non aiuterà la tua situazione.Se hai bisogno di fare qualcosa per 800 milioni di volte, puoi (a) ricorrere o (b) eseguire un ciclo (o suppongo (c) scrivere 800 milioni di chiamate alla tua funzione).Poiché il combinatore Y non esegue il ciclo, deve quindi ricorrere.

Un ciclo è ciò che stai cercando, a meno che tu non stia utilizzando un ambiente di runtime che offre una ricorsione in coda adeguata (come Scheme).

Detto questo, implementare il combinatore Y da zero nella lingua che preferisci è un esercizio eccellente.

Answer 2

I combinatori Y sono utili ma penso che tu voglia davvero l'ottimizzazione della ricorsione della coda che elimini l'uso dello stack per le funzioni ricorsive della coda.La ricorsione in coda è possibile solo quando il risultato di ogni chiamata ricorsiva viene immediatamente restituito dal chiamante e mai alcun calcolo aggiuntivo dopo la chiamata.Sfortunatamente C # non supporta l'ottimizzazione della ricorsione della coda, tuttavia puoi emularla con un trampolino che consente una semplice conversione dal metodo ricorsivo della coda a un metodo avvolto dal trampolino.

// Tail
int factorial( int n ) { return factorialTail( n, 1, 1 ); }
int factorialTail( int n, int i, int acc ) {
  if ( n < i ) return acc;
  else return factorialTail( n, i + 1, acc * i );
}

// Trampoline
int factorialTramp( int n ) { 
   var bounce = new Tuple<bool,int,int>(true,1,1);
   while( bounce.Item1 ) bounce = factorialOline( n, bounce.Item2, bounce.Item3 );
   return bounce.Item3;
}
Tuple<bool,int,int> factorialOline( int n, int i, int acc ) {
  if ( n < i ) return new Tuple<bool,int,int>(false,i,acc);
  else return new Tuple<bool,int,int>(true,i + 1,acc * i);
}

Answer 3

Puoi usare il trampolino come viene usato in Reactive Extension, ho provato a spiegarlo sul mio blog http://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/

Answer 4

Una soluzione è convertire le funzioni per utilizzare un ciclo e una struttura dati contesto esplicita. Il contesto rappresenta ciò che le persone generalmente pensano come stack di chiamate. Potresti trovare la mia risposta a un'altra domanda sulla conversione alla ricorsione in coda utile. I passaggi rilevanti sono da 1 a 5; 6 e 7 sono specifici per quella particolare funzione, mentre il tuo sembra più complicato.

L'alternativa "facile", tuttavia, è aggiungere un contatore di profondità a ciascuna delle tue funzioni; quando raggiunge un limite (determinato dalla sperimentazione), genera un nuovo thread per continuare la ricorsione con un nuovo stack. Il vecchio thread si blocca in attesa che il nuovo thread gli invii un risultato (o se vuoi essere fantasioso, un risultato o un'eccezione per rilanciare nuovamente). Il contatore di profondità torna a 0 per la nuova filettatura; quando raggiunge il limite, crea un terzo thread e così via. Se memorizzi nella cache i thread per evitare di pagare il costo di creazione del thread più spesso del necessario, si spera che otterrai prestazioni accettabili senza dover ristrutturare drasticamente il tuo programma.