Ci sono problemi che non possono essere scritti usando la ricorsione della coda?

La ricorsione della coda è un’importante strategia di ottimizzazione delle prestazioni nei linguaggi funzionali perché consente alle chiamate ricorsive di consumare stack costanti (anziché O (n)).

Ci sono problemi che semplicemente non possono essere scritti in uno stile coda-ricorsivo, o è sempre ansible convertire una funzione ricorsivamente ingenua in una coda ricorsiva?

In tal caso, un giorno i compilatori e gli interpreti possono essere abbastanza intelligenti da eseguire automaticamente la conversione?

Sì, in realtà è ansible prendere un po ‘di codice e convertire ogni chiamata di funzione – e ogni ritorno – in una coda. Quello che si finisce è chiamato continuation-passing style, o CPS.

Ad esempio, ecco una funzione contenente due chiamate ricorsive:

(define (count-tree t) (if (pair? t) (+ (count-tree (car t)) (count-tree (cdr t))) 1)) 

Ed ecco come apparirebbe se aveste convertito questa funzione in stile di passaggio continuo:

 (define (count-tree-cps t ctn) (if (pair? t) (count-tree-cps (car t) (lambda (L) (count-tree-cps (cdr t) (lambda (R) (ctn (+ LR)))))) (ctn 1))) 

L’argomento extra, ctn , è una procedura che count-tree-cps chiama-coda invece di ritornare . (La risposta di sdcvvc dice che non si può fare tutto nello spazio O (1), e questo è corretto, qui ogni continuazione è una chiusura che occupa un po ‘di memoria).

Non ho trasformato le chiamate in car o cdr o + in chiamate di coda. Anche quello potrebbe essere fatto, ma presumo che quelle chiamate foglia siano effettivamente in linea.

Adesso per la parte divertente. Chicken Scheme esegue effettivamente questa conversione su tutto il codice che compila. Le procedure compilate da Chicken non ritornano mai . C’è un articolo classico che spiega perché lo Schema di Pollo fa questo, scritto nel 1994 prima che Pollo fosse implementato: il CONS non dovrebbe difendere i suoi argomenti, Parte II: Cheney sul MTA

Sorprendentemente, lo stile di passaggio continuo è abbastanza comune in JavaScript. Puoi usarlo per eseguire calcoli di lunga durata , evitando il popup “slow script” del browser. Ed è interessante per le API asincrone. jQuery.get (un semplice wrapper su XMLHttpRequest) è chiaramente in stile di passaggio continuo; l’ultimo argomento è una funzione.

È vero ma non utile osservare che qualsiasi raccolta di funzioni reciprocamente ricorsive può essere trasformata in una funzione ricorsiva di coda. Questa osservazione è alla pari con la vecchia castagna degli anni ’60 che i costrutti del stream di controllo potrebbero essere eliminati perché ogni programma potrebbe essere scritto come un ciclo con all’interno una dichiarazione di caso.

Ciò che è utile sapere è che molte funzioni che non sono ovviamente ricorsive in coda possono essere convertite in forma ricorsiva in coda mediante l’aggiunta di parametri di accumulo . (Una versione estrema di questa trasformazione è la trasformazione in stile di passaggio continuo (CPS), ma la maggior parte dei programmatori trova l’output della trasformazione CPS difficile da leggere.)

Ecco un esempio di una funzione che è “ricorsiva” (in realtà è solo iterativa) ma non ricorsiva in coda:

 factorial n = if n == 0 then 1 else n * factorial (n-1) 

In questo caso il moltiplicarsi avviene dopo la chiamata ricorsiva. Possiamo creare una versione ricorsiva della coda inserendo il prodotto in un parametro cumulativo:

 factorial n = fn 1 where fn product = if n == 0 then product else f (n-1) (n * product) 

La funzione interna f è coda-ricorsiva e si compila in un anello stretto.


Trovo utili le seguenti distinzioni:

  • In un programma iterativo o ricorsivo, risolvi un problema di dimensione n risolvendo dapprima un sottoproblema di dimensione n-1 . Il calcolo della funzione fattoriale rientra in questa categoria e può essere fatto in modo iterativo o ricorsivo. (Questa idea generalizza, ad esempio, alla funzione di Fibonacci, dove hai bisogno sia di n-1 che di n-2 per risolvere n .)

  • In un programma ricorsivo, risolvi un problema di dimensione n risolvendo dapprima due sottoproblemi di dimensione n/2 . Oppure, più in generale, risolvi un problema di dimensione n risolvendo dapprima un sottoproblema di dimensione k e uno di dimensione nk , dove 1 < k < n . Quicksort e mergesort sono due esempi di questo tipo di problema, che può essere facilmente programmato in modo ricorsivo, ma non è così facile programmarlo in modo iterativo o utilizzare solo la ricorsione della coda. (Devi essenzialmente simulare la ricorsione usando uno stack esplicito.)

  • Nella programmazione dynamic, risolvi un problema di dimensione n risolvendo dapprima tutti i sottoproblemi di tutte le dimensioni k , dove k . Trovare il percorso più breve da un punto a un altro sulla metropolitana di Londra è un esempio di questo tipo di problema. (Il London Underground è un grafico a connessione multipla e tu risolvi il problema trovando prima tutti i punti per i quali il percorso più breve è 1 stop, quindi per il quale il percorso più breve è 2 fermate, ecc. Ecc.)

Solo il primo tipo di programma ha una trasformazione semplice in forma ricorsiva in coda.

Qualsiasi algoritmo ricorsivo può essere riscritto come un algoritmo iterativo (forse richiedendo uno stack o una lista) e gli algoritmi iterativi possono sempre essere riscritti come algoritmi di coda ricorsiva, quindi penso sia vero che qualsiasi soluzione ricorsiva può in qualche modo essere convertita in una soluzione ricorsiva di coda .

(Nei commenti, Pascal Cuoq sottolinea che qualsiasi algoritmo può essere convertito in stile di passaggio continuo ).

Si noti che solo perché qualcosa è ricorsivo in coda non significa che l’utilizzo della memoria sia costante. Significa solo che lo stack di call-return non cresce.

Non puoi fare tutto nello spazio O (1) (teorema della gerarchia spaziale). Se si insiste a utilizzare la ricorsione di coda, è ansible memorizzare lo stack di chiamate come uno degli argomenti. Ovviamente questo non cambia nulla; da qualche parte internamente, c’è uno stack di chiamate, lo stai semplicemente rendendo esplicitamente visibile.

In tal caso, un giorno i compilatori e gli interpreti possono essere abbastanza intelligenti da eseguire automaticamente la conversione?

Tale conversione non diminuirà la complessità dello spazio.

Come ha commentato Pascal Cuoq, un altro modo è usare CPS ; tutte le chiamate sono quindi ricorsive.

Non penso che qualcosa del tipo tak possa essere implementato usando solo chiamate tail. (non permettendo continuazioni)