Mi piace usare la ricorsione ogni volta che posso, sembra un modo molto più naturale per eseguire il loop su qualcosa dei loop effettivi. Mi stavo chiedendo se c'è un limite alla ricorsione in lisp? Come se ci fosse in pitone dove si spaventa dopo 1000 loop? Potresti usarlo per dire, un ciclo di gioco?C'è qualche limite alla ricorsione in lisp?
Provalo ora, conteggio semplice della funzione ricorsiva. Ora a> 7000000!
Grazie mille ottimizzazione
In primo luogo, dovresti capire di cosa tratta la coda.
Le chiamate tail sono chiamate che non consumano stack. Ora devi riconoscere quando stai consumando lo stack.
Prendiamo l'esempio del fattoriale:
(defun factorial (n)
(if (= n 1)
1
(* n (factorial (- n 1)))))
Ecco la non-coda ricorsiva attuazione fattoriale. Perché? Questo perché oltre al ritorno da fattoriale, c'è un calcolo in sospeso.
(* n ..)
Quindi si impilano n ogni volta che si chiama fattoriale. Ora scriviamo la coda fattoriale ricorsiva:
(defun factorial-opt (n &key (result 1))
(if (= n 1)
result
(factorial-opt (- n 1) :result (* result n))))
Qui, il risultato viene passato come argomento della funzione. Quindi stai anche consumando stack, ma la differenza è che le dimensioni dello stack rimangono costanti. Quindi, il compilatore può ottimizzarlo usando solo registri e lasciando lo stack vuoto.
Il factorial-opt è quindi più veloce, ma è meno leggibile. factorial è limitato alle dimensioni della pila non lo sarà factorial-opt. Quindi dovresti imparare a riconoscere la funzione ricorsiva della coda per sapere se la ricorsione è limitata.
Potrebbe esserci qualche tecnica del compilatore per trasformare una funzione ricorsiva non di coda in una coda ricorsiva. Forse qualcuno potrebbe indicare qualche link qui.
In Common Lisp, non è necessariamente vero che le chiamate tail (cioè le chiamate in posizione di coda) non consumano alcuno spazio di stack. Questo dipende dalle impostazioni di ottimizzazione e dal compilatore. –
senza dubbio ha preso il mio calcolo fattoriale dal 2700 al 3650, ma dopo di ciò ha gettato Stack over flow. Questa è una buona informazione da sapere. [Un'altra risposta utile] (http://stackoverflow.com/questions/15269193/stack-overflow-from-recursive-function-call-in-lisp) – Rorschach
mandati Schema chiamata coda, e alcune implementazioni CL offrono pure. Tuttavia, CL non lo impone.
Si noti che per ottimizzare le chiamate tail, è necessario assicurarsi che non sia necessario tornare. Per esempio. un'implementazione ingenua di Fibonacci in cui è necessario tornare e aggiungere a un'altra chiamata ricorsiva, non verrà ottimizzata la coda e di conseguenza si esaurirà lo spazio di stack.
+1 per menzionare specificamente che non tutte le ricorsioni sono chiamate tail. – Davy8
Potresti scrivermi un esempio di cosa evitare che annullerebbe la chiamata di coda? – Isaiah
@Isaiah: una semplice implementazione di un fattoriale fa: '(defun fact (n) (if (> n 0) (* n (fact (- n 1))) 1))" La ragione è che la moltiplicazione è fatta * dopo * la chiamata ricorsiva ritorna. –
Godere la ricorsione è come godersi i martelli. A volte è il miglior strumento disponibile, ma quando vuoi mettere una vite, prendi un cacciavite. – Xach
Mi piace l'idea della ricorsione. Mi affascina Tuttavia, non lo userei mai in qualsiasi cosa commerciale. Certo, rende il codice più facile da scrivere, ma a scapito dell'efficienza e del consumo di memoria. Preferisco le versioni iterative, per essere al sicuro. –