Funciones recursivas
Funciones recursivas: llamándose a sí mismas
En la entrega anterior hable sobre iteración, hoy hablaré sobre un mecanismo iterativo que se llama recursión. La recursión consiste en una función que se llama a sí misma para resolver la iteración. Normalmente la estructura recursiva implica que la función tenga una estructura similar a la siguiente:
(defun funcion-recursiva (lista-parámetros) (if (condición-de-parada) (devolver-valor definitivo) (llamar funcion-recursiva)))
Es muy importante la parte de condición-de-parada, porque si no, la
función recursiva entrará en bucle infinito. Vemos un ejemplo que
bastante habitual en los textos sobre Lisp, pero en general sobre
cualquier lenguaje que soporte la recursión.
(defun factorial (num) "Calcula de forma recursiva el factorial de un número." (if (<= num 1) 1 (* num (factorial (1- num)))))
La función se llama factorial y admite un número num como
argumento para calcular su factorial. En el bloque if la condición
de parada es cuando num es igual a 1, en ese caso, la función
devuelve 1. En otro caso, lo que se hace es multiplicar el valor de
num por el factorial de num-1. Si probamos esa función con un
num igual a 5, nos devolverá el valor de su factorial: 120.
Funciones recursivas aplicadas sobre listas
Es muy habitual encontrar en el código de Lisp una forma de iteración que utiliza las propiedades de las listas para la iteración. Consideremos el siguiente código:
(defvar lista-numeros "Una lista de cadenas con los primeros números enteros." '("uno" "dos" "tres" "cuatro")) (defun imprimir (lista) (when lista (princ (concat (car lista) ".\n")) (imprimir (cdr lista))))
Se puede ver que la recursión se extiende por la lista aprovechando
las propiedades car y cdr de la misma. El valor que condiciona la
recursión es lista, es decir, mientras el argumento pasado a la
función no sea una lista vacía '(), que sabemos es equivalente a
nil. En el ejemplo se imprime el primer elemento obtenido mediante
(car lista),1 y se llama recursivamente a imprimir con el resto de
la misma (imprimir (cdr lista)).
Desenrollando la recursión
Si tomamos el ejemplo del cálculo de factorial anterior veamos cómo evoluciona la función:
(factorial 5) (* 5 (factorial 4)) (* 5 (* 4 (factorial 3))) (* 5 (* 4 (* 3 (factorial 2)))) (* 5 (* 4 (* 3 (* 2 (factorial 1))))) (* 5 (* 4 (* 3 (* 2 1)))) (* 5 (* 4 (* 3 2))) (* 5 (* 4 6)) (* 5 24) 120
Como vemos, la recursión se desenrolla expandiéndose a una expresión más simple que luego vuelve a plegarse realizando el cálculo.
Hay ocasiones en que tanto anidamiento no es lo que queremos. Porque
en realidad lo que hace es ir «retrasando» el cálculo hasta que se ha
desenrollado toda la expresión. Podemos evitar eso haciendo una
función con un bucle while o do o loop, pero si queremos
recursión, podemos hacerlo también con una función ayudante:
(defun factorial (num) "Devuelve el factorial del número expresado por NUM." (factorial-ayudante 1 1 num)) (defun factorial-ayudante (resul contador num) "Devuelve RESUL, utilizando CONTADOR, con el NUMERO incluido." (if (> contador num) resul (factorial-ayudante (* resul contador) (1+ contador) num)))
Si hacemos como con la función recursiva anterior, los pasos serían los siguientes:
(factorial 5) (factorial-ayudante 1 1 5) (factorial-ayudante 1 2 5) (factorial-ayudante 2 3 5) (factorial-ayudante 6 4 5) (factorial-ayudante 24 5 5) (factorial-ayudante 120 6 5) 120
Como se puede apreciar no hay anidamiento y el resultado se va acumulando de una llamada a otra de la misma función.
Footnotes:
No te dejes despistar con la forma concat que sirve para
concatenar cadenas de caracteres. En el ejemplo se añade ".\n", es
decir, un punto y un salto de línea.
Comentarios