common-lisp
Herhaling
Zoeken…
Opmerkingen
Lisp wordt vaak gebruikt in educatieve contexten, waar studenten recursieve algoritmen leren begrijpen en implementeren.
Productiecode geschreven in Common Lisp of draagbare code heeft verschillende problemen met recursie: ze maken geen gebruik van implementatiespecifieke functies zoals tail call-optimalisatie , waardoor het vaak nodig is om recursie helemaal te vermijden. In deze gevallen, implementaties:
- Heeft meestal een limiet voor recursiediepte vanwege limieten in stapelformaten. Daarom zullen recursieve algoritmen alleen werken voor gegevens van beperkte omvang.
- Biedt niet altijd optimalisatie van staartoproepen, vooral in combinatie met dynamisch scoped-bewerkingen.
- Biedt alleen optimalisatie van staartoproepen op bepaalde optimalisatieniveaus.
- Biedt gewoonlijk geen optimalisatie van de staartoproep .
- Biedt meestal geen tail call-optimalisatie op bepaalde platforms. Implementaties op JVM doen dit bijvoorbeeld niet, omdat de JVM zelf geen optimalisatie van staartoproepen ondersteunt.
Het vervangen van staartoproepen door sprongen maakt debuggen meestal moeilijker; Door sprongen toe te voegen, worden stapelframes niet meer beschikbaar in een debugger. Als alternatieven biedt Common Lisp:
- Iteratieconstructies, zoals
DO,DOTIMES,LOOPen anderen - Hogere-orde functies, zoals
MAP,REDUCEen andere - Verschillende besturingsstructuren, waaronder low-level
go to
Recursiesjabloon 2 multi-conditie
(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
Recursiesjabloon 1 recursie met één voorwaarde enkele staart
(defun fn (x)
(cond (test-condition the-value)
(t (fn reduced-argument-x))))
Bereken nde Fibonacci-nummer
;;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.
)
)
)
)
Druk de elementen van een lijst recursief af
;;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))
)
)
)
Om dit te testen, voer uit:
(setq test-list '(1 2 3 4))
(print-list test-list)
Het resultaat zal zijn:
1
2
3
4
Bereken de faculteit van een geheel getal
Een eenvoudig algoritme om te implementeren als een recursieve functie is faculteit.
;;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)))
)
)
)
