common-lisp
Recursion
Buscar..
Observaciones
Lisp se usa a menudo en contextos educativos, donde los estudiantes aprenden a comprender e implementar algoritmos recursivos.
El código de producción escrito en Common Lisp o código portátil tiene varios problemas con la recursión: no hacen uso de las características específicas de la implementación, como la optimización de llamadas de cola , lo que a menudo hace que sea necesario evitar la recursión por completo. En estos casos, las implementaciones:
- Generalmente tienen un límite de profundidad de recursión debido a los límites en los tamaños de pila. Por lo tanto, los algoritmos recursivos solo funcionarán para datos de tamaño limitado.
- No siempre proporcione optimización de llamadas de cola, especialmente en combinación con operaciones de alcance dinámico.
- Solo proporciona optimización de llamadas de cola en ciertos niveles de optimización.
- No suele proporcionar optimización de llamada de cola .
- Por lo general, no proporcionan la optimización de llamadas de cola en ciertas plataformas. Por ejemplo, las implementaciones en JVM pueden no hacerlo, ya que la JVM en sí no admite la optimización de llamadas de cola .
Reemplazar llamadas de la cola por saltos generalmente hace que la depuración sea más difícil; Agregar saltos hará que los marcos de pila no estén disponibles en un depurador. Como alternativas, Common Lisp ofrece:
- Construcciones de iteración, como
DO,DOTIMES,LOOPy otras. - Funciones de orden superior, como
MAP,REDUCEy otras. - Varias estructuras de control, incluyendo bajo nivel
go to
Recursión de plantilla 2 de múltiples condiciones.
(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
Recursión plantilla 1 sola condición recursión de cola única
(defun fn (x)
(cond (test-condition the-value)
(t (fn reduced-argument-x))))
Calcular el número de 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.
)
)
)
)
Imprimir recursivamente los elementos de una lista
;;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))
)
)
)
Para probar esto, ejecute:
(setq test-list '(1 2 3 4))
(print-list test-list)
El resultado será:
1
2
3
4
Calcular el factorial de un número entero
Un algoritmo fácil de implementar como función recursiva es factorial.
;;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)))
)
)
)