Le lingue funzionali sono migliori in fase di ricorsione?

Sì, lo fanno, ma non solo perché possono , ma perché devono .

Il concetto chiave qui è purezza : una funzione pura è una funzione senza effetti collaterali e senza stato. I linguaggi di programmazione funzionale generalmente abbracciano la purezza per molte ragioni, come ragionare sul codice ed evitare dipendenze non ovvie. Alcune lingue, in particolare Haskell, arrivano addirittura a permettere il solo codice puro; eventuali effetti collaterali che un programma può avere (come l'esecuzione di I / O) vengono spostati su un runtime non puro, mantenendo puro il linguaggio stesso.

Non avere effetti collaterali significa che non puoi avere contatori di loop (perché un contatore di loop costituirebbe uno stato mutabile, e modificare tale stato sarebbe un effetto collaterale), quindi il più iterativo che un linguaggio puramente funzionale può ottenere è iterare su un elenco (questa operazione viene in genere chiamata foreach o map ). La ricorsione, tuttavia, è una corrispondenza naturale con la pura programmazione funzionale: non è necessario alcuno stato per recurse, eccetto per gli argomenti della funzione (sola lettura) e un valore di ritorno (di sola scrittura).

Tuttavia, non avere effetti collaterali significa anche che la ricorsione può essere implementata in modo più efficiente e che il compilatore può ottimizzarla in modo più aggressivo. Non ho studiato a fondo un compilatore di questo tipo, ma per quanto posso dire, la maggior parte dei compilatori di linguaggi di programmazione funzionali eseguono un'ottimizzazione delle chiamate tail, e alcuni possono persino compilare certi tipi di costrutti ricorsivi in loop dietro le quinte.

Stai comparando ricorsione vs iterazione. Senza eliminazione di coda di chiamata , l'iterazione è effettivamente più efficiente perché non c'è alcuna chiamata di funzione aggiuntiva. Inoltre, l'iterazione può continuare all'infinito, mentre è possibile esaurire lo spazio di stack da troppe chiamate di funzione.

Tuttavia, l'iterazione richiede la modifica di un contatore. Ciò significa che deve esistere una variabile mutabile , che è vietata in un ambito puramente funzionale. Quindi i linguaggi funzionali sono progettati appositamente per funzionare senza necessità di iterazione, da cui le chiamate di funzioni semplificate.

Ma nessuno di questi si occupa del perché il tuo codice di esempio sia così elegante. Il tuo esempio dimostra una proprietà diversa, ovvero corrispondenza del modello . Ecco perché l'esempio di Haskell non ha condizionali espliciti. In altre parole, non è la ricorsione semplificata a rendere piccolo il tuo codice; è la corrispondenza del modello.

Tecnicamente no, ma praticamente sì.

La ricorsione è molto più comune quando si sta affrontando un approccio funzionale al problema. Pertanto, i linguaggi progettati per utilizzare un approccio funzionale spesso includono funzionalità che rendono la ricorsione più semplice / migliore / meno problematica. Fuori dalla mia testa, ce ne sono tre in comune:

1. Ottimizzazione delle chiamate tail. Come sottolineato da altri poster, i linguaggi funzionali richiedono spesso TCO.

2. Valutazione pigra. Haskell (e alcune altre lingue) viene valutato pigramente. Questo ritarda il "lavoro" effettivo di un metodo finché non è richiesto. Questo tende a portare a strutture dati ricorsive e per estensione, metodi ricorsivi per lavorarci sopra.

3. Immutabilità. La maggior parte delle cose con cui lavori nei linguaggi di programmazione funzionale è immutabile. Questo facilita la ricorsione perché non devi preoccuparti dello stato degli oggetti nel tempo. Ad esempio, non è possibile modificare un valore da sotto di te. Inoltre, molte lingue sono progettate per rilevare pure funzioni . Poiché le funzioni pure non hanno effetti collaterali, il compilatore ha molta più libertà su quale ordine eseguano le funzioni e altre ottimizzazioni.

Nessuna di queste cose è veramente specifica per le lingue funzionali rispetto ad altre, quindi non sono semplicemente migliori perché sono funzionali. Ma poiché sono funzionali, le decisioni di progettazione adottate tenderanno a queste caratteristiche perché sono più utili (e i loro aspetti negativi meno problematici) durante la programmazione dal punto di vista funzionale.

Haskell e altri linguaggi funzionali generalmente usano la valutazione lazy. Questa funzione ti consente di scrivere funzioni ricorsive senza fine.

Se si scrive una funzione ricorsiva senza definire un caso base in cui termina la ricorsione, si finisce con chiamate infinite a tale funzione e stackoverflow.

Haskell supporta anche ottimizzazioni delle chiamate a funzioni ricorsive. In Java ogni chiamata di funzione si accumulerebbe e causerebbe un sovraccarico.

Quindi sì, i linguaggi funzionali gestiscono la ricorsione meglio di altri.

L'unica ragione tecnica che conosco è che alcuni linguaggi funzionali (e alcune lingue imperative se ricordo) hanno quello che viene chiamato ottimizzazione chiamata coda che consente a un metodo ricorsivo di non aumentare la dimensione dello stack con ogni chiamata ricorsiva (ovvero la chiamata ricorsiva più o meno sostituisce la chiamata corrente nello stack).

Nota che questa ottimizzazione non funziona su qualsiasi chiamata ricorsiva, solo metodi ricorsivi tail-call (cioè metodi che non mantengono lo stato al momento della chiamata ricorsiva)

Ti consigliamo di esaminare Garbage Collection è veloce, ma uno stack è più veloce , un documento su usando ciò che i programmatori C considererebbero come "heap" per i frame dello stack nella compilazione C. Credo che l'autore abbia armeggiato con Gcc per farlo. Non è una risposta definitiva, ma potrebbe aiutarti a capire alcuni dei problemi con la ricorsione.

Il linguaggio di programmazione Alef , che era solito affiancare a Plan 9 di Bell Labs , aveva una dichiarazione "diventa" (vedi sezione 6.6.4 di questo riferimento ). È una sorta di ottimizzazione della ricorsione di coda chiamata esplicita. Il "ma usa lo stack delle chiamate!" l'argomento contro la ricorsione potrebbe essere eliminato.

TL; DR: Sì, lo fanno
La ricorsione è uno strumento chiave nella programmazione funzionale e quindi è stato fatto molto lavoro per ottimizzare queste chiamate. Ad esempio, R5RS richiede (nelle specifiche!) Che tutte le implementazioni gestiscano le chiamate di ricorsione in coda non associate senza che il programmatore si preoccupi dell'overflow dello stack. Per confronto, per impostazione predefinita il compilatore C non eseguirà nemmeno un'ovvia ottimizzazione di coda (prova un reverse ricorsivo di una lista collegata) e dopo alcune chiamate, il programma terminerà (il compilatore ottimizzerà, se si usa - O2).

Naturalmente, nei programmi scritti in modo orribile, come il famoso esempio di fib che è esponenziale, il compilatore ha poche o nessuna possibilità di fare la sua "magia". Quindi bisogna fare attenzione a non ostacolare gli sforzi del compilatore nell'ottimizzazione.

EDIT: per l'esempio fib, intendo il seguente:

(define (fib n)
 (if (< n 3) 1 
  (+ (fib (- n 1)) (fib (- n 2)))
 )
)

I linguaggi funzionali sono migliori in due tipi molto specifici di ricorsione: ricorsione della coda e ricorsione infinita. Sono altrettanto brutte delle altre lingue con altri tipi di ricorsione, come il tuo esempio di factorial .

Questo non vuol dire che non ci siano algoritmi che funzionano bene con la ricorsione regolare in entrambi i paradigmi. Ad esempio, tutto ciò che richiede comunque una struttura di dati simile allo stack, come una ricerca ad albero in profondità, è la più semplice da implementare con la ricorsione.

La ricorsione si presenta più spesso con la programmazione funzionale, ma è anche abusata, specialmente dai principianti o nei tutorial per principianti, forse perché molti principianti alla programmazione funzionale hanno usato la ricorsione prima nella programmazione imperativa. Esistono altri costrutti di programmazione funzionale, come le list comprehensions, le funzioni di ordine superiore e altre operazioni sulle raccolte, che di solito sono molto più adatte concettualmente, per stile, per concisione, per efficienza e per capacità di ottimizzazione.

Ad esempio, il suggerimento di delnan su factorial n = product [1..n] non è solo più conciso e più facile da leggere, ma è anche altamente parallelizzabile. Lo stesso vale per l'utilizzo di fold o reduce se la tua lingua non ha una product già incorporata. La ricorsione è la soluzione di ultima istanza per questo problema. Il motivo principale per cui lo vedi risolto ricorsivamente nei tutorial è come un punto di partenza prima di arrivare a soluzioni migliori, non come un esempio di best practice.