Potresti utilizzare un semi-co-routine o generatore . Non esistono in tutte le lingue e non sempre consentono direttamente la ricorsione. Ma la capacità di farlo e la disponibilità di semicoroutine non dipendono dalla disponibilità di thread (concessi, sono molto più facili da implementare con thread o fibre , quindi sono probabilmente più prontamente disponibili su alcuni piattaforme rispetto ad altre).
Questo è per gli scenari in cui le soluzioni sono esplorate in modo iterativo ma senza una particolare gerarchia. In questo caso ottieni una soluzione dopo l'altra e se il chiamante vuole la prossima soluzione, richiama semplicemente la funzione, che "ricomincerà" la ricerca.
Nella maggior parte dei casi hai uno scenario leggermente diverso in cui l'algoritmo di ricerca della soluzione esplora una parte (più o meno grande) dello spazio delle fasi e classifica le possibili soluzioni, restituendo il migliore secondo alcuni metrica. Chiamando di nuovo la funzione che non vuoi un'altra soluzione, vuoi il secondo migliore (e così via). In tal caso, tranne nei casi specifici in cui la struttura del problema potrebbe esserti d'aiuto, la funzione deve mantenere uno "stack" delle soluzioni trovate finora nel ramo di scelta corrente (invece di restituire semplicemente il migliore di un dato ramo di scelta), che complica in qualche modo i requisiti di memoria. Inoltre, la funzione dovrà restituire un array. Potrebbe essere necessario specificare la profondità dello stack restituito, ad esempio venti, e accettare di poter chiamare il semicoroutine diciannove volte al massimo, prima di ottenere un errore (o ottenere tutte e venti le soluzioni in un colpo solo, ma non di più). La routine dovrà anche unire e ordinare la pila dei suoi figli di chiamata (ad esempio in un albero, la ricorsione a sinistra restituirà venti soluzioni, la ricorsione giusta un'altra quindicina e il chiamante si unirà, ordinandole in una nuova pila di venti, e decidere se cederne uno o passare i venti indietro).
Potresti quindi finire (invece di ottenere la soluzione 1 nel tempo T, la soluzione 2 nel tempo 0,2T e così via) ottenendo venti soluzioni in 10 volte il tempo, cioè 10 volte è il tempo necessario per la restituzione della prima soluzione.
La soluzione di cui sopra può essere implementata più facilmente a partire da una funzione ricorsiva, invece di chiamare
var a := findSolution(phaseSpace)
avresti
var a[] := findSolutions(phaseSpace, 20)
Infine, in alcuni scenari la ricorrenza converge sulla soluzione migliore, e gli altri sono "lasciati indietro" in modo tale che non è facile recuperarli, né ci si può aspettare che salvi l'intero stato di stack della funzione per tutti i rami possibili. Per affrontare questo caso è necessario passare alla funzione ricorsiva un elenco di quelle soluzioni già restituite, che devono essere considerate come invalidate, e la funzione dovrà quindi ricominciare da capo ogni volta , ciascuna tempo potenzialmente esplorando diversi rami di scelta. E ottieni 20 soluzioni, ad esempio, 30 volte il tempo (ma il tempo per la prima soluzione è ancora 1T).