Notxor tiene un blog

Defenestrando la vida


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.

Nota al pie de página:

1

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