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:
Se analizan dos condiciones:
![]() 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 RECURSIVALa 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.
Si antes de ejecutar esta función invocamos la función TRACE:
podemos seguir en la ventana TRACE de Visual LISP los pasos seguidos en la evaluación de esta función:
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.
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 AUTOCADComo 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
|
Apuntes para un Curso... > Programación de Aplicaciones Gráficas > 2. Técnicas Fundamentales > 2.4. Funciones Recursivas e Iterativas >