common-lisp
Rekursion
Suche…
Bemerkungen
Lisp wird häufig in Bildungskontexten eingesetzt, in denen die Schüler rekursive Algorithmen verstehen und implementieren lernen.
Produktionscode, der in Common Lisp oder Portable Code geschrieben wurde, hat mehrere Probleme mit der Rekursion: Sie verwenden keine implementierungsspezifischen Funktionen wie die Optimierung von Rückrufen , was oft eine Rekursion ganz erforderlich macht. In diesen Fällen Implementierungen:
- Üblicherweise haben Sie eine Rekursionstiefenbegrenzung aufgrund von Begrenzungen bei Stapelgrößen. Rekursive Algorithmen funktionieren daher nur für Daten begrenzter Größe.
- Bieten Sie nicht immer eine Optimierung von Abrufaufrufen an, insbesondere in Kombination mit Operationen mit dynamischen Bereichen.
- Bieten Sie nur bei bestimmten Optimierungsstufen eine Optimierung der Rückrufe an.
- Stellen Sie normalerweise keine Rückrufoptimierung bereit.
- Normalerweise bieten keine Endaufruf Optimierung auf bestimmten Plattformen. Beispielsweise können Implementierungen in der JVM dies möglicherweise nicht tun, da die JVM selbst keine Tail Call-Optimierung unterstützt .
Das Ersetzen von Tail Calls durch Sprünge macht das Debuggen normalerweise schwieriger. Durch das Hinzufügen von Sprüngen werden Stack-Frames in einem Debugger nicht verfügbar. Als Alternative bietet Common Lisp:
- Iterationskonstrukte wie
DO,DOTIMES,LOOPund andere - Funktionen höherer Ordnung wie
MAP,REDUCEund andere - Verschiedene Kontrollstrukturen, einschließlich Low-Level,
go to
Rekursionsschablone 2 mit mehreren Bedingungen
(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
Rekursionsvorlage 1 Einzelbedingung Rekursion einzelner Endpunkt
(defun fn (x)
(cond (test-condition the-value)
(t (fn reduced-argument-x))))
N-te Fibonacci-Zahl berechnen
;;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.
)
)
)
)
Rekursiv die Elemente einer Liste drucken
;;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))
)
)
)
Um dies zu testen, führen Sie Folgendes aus:
(setq test-list '(1 2 3 4))
(print-list test-list)
Das Ergebnis wird sein:
1
2
3
4
Berechnen Sie die Fakultät einer ganzen Zahl
Ein einfacher Algorithmus, der als rekursive Funktion implementiert werden kann, ist faktoriell.
;;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)))
)
)
)