Programación recursiva frente a iterativa
Características de la programación recursiva:
Implementación intuitiva y elegante. La traducción de la solución recursiva de un problema (caso base y caso recursivo) a código Lisp es prácticamente inmediata.
Útil para optimizar cálculos. Las estructuras de datos en Lisp hacen un uso implíctito de los punteros, como en las listas:
NIL ó
Un cons cuyo cdr es, a su vez, una lista
Útil cuando hay varios niveles de anidamiento. La solución para un nivel es válida para el resto.
Formas de hacer versión iterativa:
Con mapcar
Con bucles (dolist, dotimes, etc. Desaconsejado).
Ejemplos de recursividad, (1)
Ejemplo del cálculo de la potencia de un número optimizada
> (defun potencia (x n)
;; “Optimizacion calculo potencia"
(cond ((= n 0) 1)
((evenp n) (expt (potencia x (/ n 2)) 2)
)
(t (* x (potencia x (- n 1))))))
> (potencia 2 3)
8
La interpretación y comprensión del código es compleja. Por ello es importante llegar a un compromiso entre la claridad de la programación y la eficiencia en la misma.
Ejemplos de recursividad, (2)
Contar los átomos de cualquier expresión LISP:
> (cuenta-atomos '(a (b c) ((d e) f)))
6
> (defun cuenta-atomos (expr)
(cond ((null expr) 0)
((atom expr) 1)
(t (+ (cuenta-atomos (first expr))
(cuenta-atomos (rest expr))))))
Ejemplos de recursividad, (3)
Aplanar una lista:
(aplana ‘(a (b c) ((d e) f))) >>>
(A B C D E F)
> (defun aplana (lista)
(cond
((null lista) NIL)
((atom (first lista))
(cons
(first lista)
(aplana (rest lista))))
(t (append
(aplana (first lista))
(aplana (rest lista))))))
Ejemplos de recursividad, (4)
Número de sublistas de una lista (número de veces que se abre paréntesis, menos 1):
(sublistas ‘(a (b c) ((d e) f))) >>>
3
> (defun sublistas (expresion)
(cond ((or (null expresion) (atom expresion))
0)
(t (+ (if (atom (first expresion)) 0 1)
(sublistas (first expresion))
(sublistas (rest expresion))))))
Ejemplos de recursividad, (5)
Producto escalar:
(producto '(2 3) '(4 5)) >>> 23
2 x 4 + 3 x 5 = 23
Versiones válidas:
Versión recursiva:
> (defun producto (vector1 vector2)
(if (or (null vector1) (null vector2))
0
(+ (* (first vector1) (first vector2))
(producto (rest vector1) (rest vector2)))))
Versión con mapcar
>(defun producto (vector1 vector2)
(apply #'+ (mapcar #'* vector1 vector2)))
Ejemplos de recursividad, (6)
Versión no válida del producto escalar:
Versión iterativa (no recomendable):
> (defun producto (vector1 vector2)
(let ((suma 0))
(dotimes (i (length vector1))
(setf suma
(+ suma (* (nth i vector1)
(nth i vector2)))))
suma))
Ejemplos de recursividad, (7)
> (defun profundidad-maxima (expresion)
(cond ((null expresion) 0)
((atom expresion) 1)
(t (+ 1
(apply #'max
(mapcar
#'profundidad-maxima
expresion))))))
>>> PROFUNDIDAD-MAXIMA
> (profundidad-maxima '(1))
>>>> 2
> (profundidad-maxima '((1 (2 (3))) 4))
>>>> 5
Repaso de operadores, (1)
Recordemos los siguientes operadores:
COUNT-IF, FIND-IF, REMOVE-IF, REMOVE-IF-NOT, DELETE-IF, DELETE-IF-NOT
COUNT / COUNT-IF
Contar apariciones:
(count
[:test ])
(count 2 ‘(1 2 3 4 2 4 5 2))
3
Contar los elementos que cumplen /no cumplen una condición de una lista
(count-if[-not]
(count-if ‘oddp ‘(1 2 3 4 5 6))
3
Repaso de operadores, (2)
FIND / FIND-IF
Devuelve la primera aparición:
(find
[:test ])
(find 2 ‘(1 2 3 4 2 4 5 2))
2
Devuelve el primer elemento que cumple/o no cumple el predicado
(find-if[-not]
(find-if ‘oddp '(1 2 3 4 2 4 5 2))
1
REMOVE / REMOVE-IF
Borrar las apariciones de un elemento indicado
(remove
[:test ])
(remove 2 ‘(1 2 3 4 2 4 5 2))
(1 3 4 4 5)
Elimina los que cumple/o no cumple el predicado
(remove-if[-not]
(remove-if ‘oddp '(1 2 3 4 2 4 5 2))
(2 4 2 4 2)
Ejemplos de recursividad, (8)
Objetivo: sin utilizar remove-if, conseguir la misma funcionalidad del operador:
(quitar-si ‘evenp '(1 2 3 4))
(1 3)
Versiones válidas:
Versión recursiva:
(defun quitar-si (predicado lista)
(cond
((null lista) nil)
((funcall predicado (car lista))
(quitar-si predicado (cdr lista)))
(t (cons (car lista)
(quitar-si predicado (cdr lista))))))
Versión con mapcar
(defun quitar-si (predicado lista)
(delete
NIL
(mapcar #'(lambda (elemento)
(when
(not (funcall predicado elemento))
elemento))
lista)))
Recorriendo la lista con dolist:
(defun QUITAR-SI (predicado lista)
(let (listaaux)
(dolist (i lista listaaux)
(if (not (eval (list predicado i)))
(setf listaaux (append listaaux (list i)))
)
)
)
)
Ejemplos de recursividad, (9)
Versión errónea:
Mal uso de mapcar. El hecho de que hagamos uso de mapcar no garantiza la corrección del código programado.
(defun QUITAR-SI2 (predicado lista)
(mapcar
#’(lambda (elemento)
(if (apply predicado (list elemento))
(remove elemento lista))
)
lista))
> (QUITAR-SI2 'evenp '(1 2 3 4))
(NIL (1 3 4) NIL (1 2 3))
Ejemplos de recursividad, (10)