El ejemplo clásico de una función recursiva es el cálculo del factorial de un número. Por ejemplo, 4! (factorial) es igual a 4 X 3 X 2 X 1. Algebraicamente, podemos considerar un factorial como (n!) as n X (n-1) X (n-2) X (n-3)...(n - (n+1)). Ésta sería la definición recursiva del factorial:

(defun factorial (n)
  (cond	((zerop n) 1)
	 (T 
    (* n (factorial (1- n))))
  ) ;_ fin de cond
) ;_ fin de defun

Se analizan dos condiciones:

1. que el argumento recibido sea cero (predicado ZEROP). En ese caso se devuelve 1.
2. en cualquier otro caso, se multiplica el argumento por el resultado que devuelve aplicar de nuevo la función de usuario factorial al argumento menos 1. Lógicamente la evaluación de esta operación deberá esperar al resultado de la nueva llamada a la función factorial, que si aún no es cero, provocará una nueva llamada a la misma función factorial y quedará a la espera de que esta sea evaluada y así sucesivamente. Al llegar a cero el argumento pasado a factorial, ya no se producirá una nueva llamada a la función y se comenzará a devolver respuestas a todas la evaluaciones que han quedado pendientes. Este comportamiento puede verse claramente en la ventana TRACE de visua LISP, después de haber evaluado la función (trace factorial) .

La recursión, aunque aporta soluciones de gran elegancia, debe ser utilizada con cautela. Lo ideal sería usarla con funciones que no utilicen, o utilicen muy pocos argumentos, ya que la recursión coloca cada vez una nueva copia de la función en la memoria de pila junto con sus argumentos. Es muy posible que una función efectúe tantas recursiones que se agote la memoria disponible provocando un error de desbordamiento de la pila.

Para más detalles, consultar el artículo WHAT IS RECURSION? de Glenn Grotzinger.

ANÁLISIS DE UNA FUNCIÓN RECURSIVA

La siguiente función demuestra la posibilidad de desarrollar funciones de usuario a partir de un corto número de primitivas. La función BUSCA_EN_LISTA recibe como argumentos una expresión cualquiera y una lista. En caso que la expresión esté contenida en la lista, la función devolverá la expresión y todos los términos de la lista que ocurren después de la expresión. Si expresión no pertenece a la lista, la función devuelve nil. Los resultados obtenidos son los mismos que los de la función primitiva MEMBER. De hecho muchas de las funciones hoy incorporadas a cualquiera de los dialectos modernos de LISP surgieron como funciones utilitarias que eran incorporadas de manera habitual por los usuarios.

;;;Función recursiva busca_en_lista.
;;;Equivale a la función member de LISP
;;;Esta función ha sido adaptada del tutorial
;;;LISP del ELM Research Group
(defun busca_en_lista (expresion lista)
  (cond
    ((null lista) nil)                         ;si lista está vacía o se acaba
    ((equal expresion (car lista)) lista)      ;si se encuentra expresion
    (t (busca_en_lista expresion (cdr lista))) ;en otro caso se efctúa la 
                                               ;recursión
  )
)

_$ (busca_en_lista '(a b) (list 2 r "sdf" '(a b) "KLM" 77 21 jfk))
((A B) "KLM" 77 21 nil)
_$ (member '(a b) (list 2 r "sdf" '(a b) "KLM" 77 21 jfk))
((A B) "KLM" 77 21 nil)
_$ 

Si antes de ejecutar esta función invocamos la función TRACE:

(trace busca_en_lista)

podemos seguir en la ventana TRACE de Visual LISP los pasos seguidos en la evaluación de esta función:

Entering (BUSCA_EN_LISTA (A B) (2 nil "sdf" (A B) "KLM" 77 21 nil))
  Entering (BUSCA_EN_LISTA (A B) (nil "sdf" (A B) "KLM" 77 21 nil))
    Entering (BUSCA_EN_LISTA (A B) ("sdf" (A B) "KLM" 77 21 nil))
      Entering (BUSCA_EN_LISTA (A B) ((A B) "KLM" 77 21 nil))
      Result:  ((A B) "KLM" 77 21 nil)
    Result:  ((A B) "KLM" 77 21 nil)
  Result:  ((A B) "KLM" 77 21 nil)
Result:  ((A B) "KLM" 77 21 nil)

Los objetivos perseguidos implican el recorrido de la lista, elemento a elemento, comparando cada uno con la expresión dada. La manera más sencilla para extraer un elemento de la lista (el primero) es utilizar la función CAR. Un segundo elemento pudiera extraerse con CADR y así sucesivamente. Pero este método sería demasiado rígido si queremos que la función sea aplicable a una lista de cualquier longitud.

Una solución estaría en que si el primer elemento no es el buscado, volviéramos a ejecutar la función pero que esta vez el segundo argumento (lista) fuera el resto de la lista, quitando el primer término ya analizado: (cdr lista).

Así continuaríamos probando el primer término (CAR de la lista) del resto (CDR) de la lista hasta que o termine la lista o que el primer término sea el elemento buscado.

Las condiciones que se prueban corresponden a los tres casos posibles al suministrar a la función BUSCA_EN_LISTA dos argumentos, el primero de los cuales puede ser un átomo o una lista y el segundo debe evaluar como una lista, incluso vacía.

Primer caso: ((null lista) nil)

Cuando se encuentra esta condición, la evaluación termina. La función evaluará en este caso como nil, señalando que el término no ha sido encontrado. Este sería también el caso si el segundo argumento fuera una lista vacía.

Segundo caso: ((equal expresion (car lista)) lista)

Al igual que en el primer caso, la evaluación termina. Pero en este caso el primer término de la lista (car lista) es el término buscado, y se devuelve el valor de lista.

Tercer caso: (t (busca_en_lista expresion (cdr lista)))

Este es el caso en que se produce la recursión. Siempre que lista no esté vacía (null lista) y que el primer elemento de lista no sea igual al término buscado, se llama de nuevo a la función BUSCA_EN_LISTA pero esta vez se le pasa como argumento lista (cdr lista), el resto de la lista, desechando el primer término. Así a cada ciclo, lista se acorta en un término. Al final, si expresion no formara parte de lista, la recursión terminaría al llegar a ser una lista nula.

Si observamos lo devuelto en la ventana TRACE por una y otra de estas dos funciones recursivas, observamos una diferencia. Lo devuelto por el último nivel de recursión en la función FACTORIAL es diferente a lo devuelto por el nivel superior. De hecho cada nivel devuelve un resultado diferente. Para llegar al resultado definitivo, debemos esperar a lo que devuelve cada uno de los ciclos de la recursión. Sin embargo, en la segunda función BUSCA_EN_LISTA, el resultado del último nivel es ya el resultado definitivo. Es evidente que resulta una pérdida de tiempo el esperar a que cada nivel devuelva ese mismo resultado hasta llegar al nivel superior. Los compiladores LISP más avanzados reconocerán una función de este tipo y cortarán el proceso en el instante que se obtiene el resultado del último nivel, mejorando sustancialmente la velocidad de operación de las funciones. Este tipo de funciones recursivas se conocen por el término inglés de TAIL-RECURSIVE (~ recursivas por la cola).

En muchos casos, hacer una función recursiva por la cola (tail-recursive) es posible empleando técnicas adecuadas de programación. Siempre que esto se logre podemos esperar un incremento significativo en la eficacia de los programas.

Nota: Según afirma Reini Urban, VLISP no es capaz de reconocer la recursividad por la cola o tail-recursion, de manera que aún resulta en una utilización exhaustiva de la memoria de pila (stack). Sobre los límites valores máximos admitidos de anidación (tamaño de pila) dicho autor propone ejemplos en http://xarch.tu-graz.ac.at/autocad/stdlib/STDINIT2.LSP

SU UTILIZACIÓN PRÁCTICA DENTRO DE AUTOCAD

Como ejemplo de la utilidad de los métodos de programación expuestos, desarrollaremos un programa encaminado a resolver un problema concreto dentro de la aplicación. En ocasiones tenemos la necesidad de extraer la información de las coordenadas de los vértices de una polilínea. En este caso analizaremos una polilínea del tipo LWPOLYLINE, que se introdujo con la versión 14 de AutoCAD. Las entidades de AutoCAD guardan su información en forma de listas de asociación, una lista con sublistas donde el número inicial de cada sublista identifica el tipo de dato de que se trata. Un proceso recursivo sería especialmente adecuado para recorrer dicha lista extrayendo de ella la información requerida. Pasaremos entonces a estudiar el desarrollo de una FUNCIÓN RECURSIVA PARA LA LECTURA DE LOS VÉRTICES DE UNA POLILÍNEA

---

Inicio | Índice | Continuar...