common-lisp
ricorsione
Ricerca…
Osservazioni
Il Lisp viene spesso utilizzato in contesti educativi, in cui gli studenti imparano a comprendere e implementare algoritmi ricorsivi.
Il codice di produzione scritto in codice Common Lisp o portatile presenta diversi problemi con la ricorsione: non fanno uso di funzionalità specifiche dell'implementazione come l' ottimizzazione delle chiamate tail , spesso rendendo necessario evitare del tutto la ricorsione. In questi casi, implementazioni:
- Di solito hanno un limite di profondità di ricorsione a causa dei limiti nelle dimensioni dello stack. Pertanto, gli algoritmi ricorsivi funzioneranno solo con dati di dimensioni limitate.
- Non sempre offrono l'ottimizzazione delle chiamate tail, soprattutto in combinazione con operazioni con scope dinamiche.
- Fornisce solo l'ottimizzazione delle chiamate tail a determinati livelli di ottimizzazione.
- Di solito non offrono l' ottimizzazione della chiamata di coda .
- Di solito non offrono l' ottimizzazione della chiamata di coda su alcune piattaforme. Ad esempio, le implementazioni su JVM potrebbero non farlo, poiché la stessa JVM non supporta l' ottimizzazione delle chiamate tail .
Sostituire le chiamate di coda con i salti di solito rende più difficile il debugging; L'aggiunta di salti farà sì che i frame dello stack diventino non disponibili in un debugger. In alternativa, Common Lisp fornisce:
- Costrutti di
DOTIMES, comeDO,DOTIMES,LOOPe altri - Funzioni di ordine superiore, come
MAP,REDUCEe altro - Varie strutture di controllo, incluso il basso livello,
go to
Ricorsione modello 2 multi-condizione
(defun fn (x)
(cond (test-condition1 the-value1)
(test-condition2 the-value2)
...
...
...
(t (fn reduced-argument-x))))
CL-USER 2788 > (defun my-fib (n)
(cond ((= n 1) 1)
((= n 2) 1)
(t (+
(my-fib (- n 1))
(my-fib (- n 2))))))
MY-FIB
CL-USER 2789 > (my-fib 1)
1
CL-USER 2790 > (my-fib 2)
1
CL-USER 2791 > (my-fib 3)
2
CL-USER 2792 > (my-fib 4)
3
CL-USER 2793 > (my-fib 5)
5
CL-USER 2794 > (my-fib 6)
8
CL-USER 2795 > (my-fib 7)
13
Ricorsione modello 1 singola condizione di ricorsione a coda singola
(defun fn (x)
(cond (test-condition the-value)
(t (fn reduced-argument-x))))
Calcola n numero di Fibonacci
;;Find the nth Fibonacci number for any n > 0.
;; Precondition: n > 0, n is an integer. Behavior undefined otherwise.
(defun fibonacci (n)
(cond
( ;; Base case.
;; The first two Fibonacci numbers (indices 1 and 2) are 1 by definition.
(<= n 2) ;; If n <= 2
1 ;; then return 1.
)
(t ;; else
(+ ;; return the sum of
;; the results of calling
(fibonacci (- n 1)) ;; fibonacci(n-1) and
(fibonacci (- n 2)) ;; fibonacci(n-2).
;; This is the recursive case.
)
)
)
)
Stampa ricorsivamente gli elementi di un elenco
;;Recursively print the elements of a list
(defun print-list (elements)
(cond
((null elements) '()) ;; Base case: There are no elements that have yet to be printed. Don't do anything and return a null list.
(t
;; Recursive case
;; Print the next element.
(write-line (write-to-string (car elements)))
;; Recurse on the rest of the list.
(print-list (cdr elements))
)
)
)
Per verificare ciò, eseguire:
(setq test-list '(1 2 3 4))
(print-list test-list)
Il risultato sarà:
1
2
3
4
Calcola il fattoriale di un numero intero
Un semplice algoritmo da implementare come funzione ricorsiva è fattoriale.
;;Compute the factorial for any n >= 0. Precondition: n >= 0, n is an integer.
(defun factorial (n)
(cond
((= n 0) 1) ;; Special case, 0! = 1
((= n 1) 1) ;; Base case, 1! = 1
(t
;; Recursive case
;; Multiply n by the factorial of n - 1.
(* n (factorial (- n 1)))
)
)
)