Programación recursiva con Python

Supongo que a todos nos han dicho alguna vez, seguramente durante el paso por el colegio, que no se puede definir algo en términos de sí mismo. Esta norma está muy bien para definir conceptos o palabras ya que, de caer en este error, estaríamos tratando de explicar algo nuevo en términos de algo desconocido. Sin embargo, en matemáticas puede ser muy útil, e incluso elegante, definir problemas de forma recurrente. Lo mismo ocurre a la hora de programar. La programación iterativa está mucho más extendida que la recursiva (¿quizás por motivos de eficiencia?) y, sin embargo, esta última puede ayudarnos a simplificar y reducir el código.

Como os decía, es habitual en matemáticas definir problemas de forma recurrente. Podemos definir el factorial de un número n cualquiera como el producto de los número del 1 a n, esto es:

La alternativa recursiva o recurrente (¿son sinónimos?) sería la siguiente:

Es decir, estaríamos definiendo el factorial de un número n en términos del factorial de ese mismo número reducido una unidad. Bueno, vale, siendo rigurosos estas definiciones no son exactamente equivalentes. A la última habría que añadir que, por definición, el factorial de 1 es 1. Y a las dos les podríamos añadir también que el factorial de 0 es 1 (para la tranquilidad de algunos e indiferencia de muchos otros).

La condición extra que tuve que añadir a la segunda definición, lejos de ser un detalle sin importancia, va a ser clave cuando programemos recursivamente. La idea detrás de programar de esta forma es simplificar un problema en términos del mismo problema, pero más sencillo, hasta llegar a un caso base. En el caso del factorial, hasta llegar al factorial de 1.

Vamos a definir una función en Python que nos devuelva el factorial de un número. Pero vamos a definirla recursivamente con todo lo que mencioné hasta ahora.

def factorial(num):
   if num == 0 or num == 1:
      return 1
   else:
      return num * factorial(num - 1)

Salvo en los casos base, cuando num vale 0 o 1, el primer condicional no se cumplirá así que se avanzará hacia el código en else, donde la función devolverá el producto de num por (¡sorpresa!) factorial(num - 1), una llamada a la función que estamos definiendo. Imaginemos el caso en que num toma el valor 2. La segunda llamada a la función factorial sería con el valor 1, que es un caso base y devolvería el valor 1. Así que ya tendríamos el valor final, que sería 2 por 1. Para números mayores el razonamiento es el mismo. Podéis visualizar el funcionamiento de este código, paso a paso, para el caso en que num vale 5 utilizando Python Tutor.

Antes de pasar a otro ejemplo me gustaría aclarar un concepto muy importante en Python y otros lenguajes de programación: el ámbito o scope de las variables. Se define el scope de una variable como la parte del programa desde donde es accesible. Cuando definimos una variable en el cuerpo principal del programa decimos que se trata de una variable global, esto es, una variable que es accesible desde todos los lugares. Sin embargo, una variable definida dentro de una función es una variable local, y su scope se reduce a los límites de esa función. Además, cada vez que llamemos a una función se creará un scope independiente de los demás, que será “destruido” cuando la función termine de ejecutarse. Por si ya fuera poco lío, podemos forzar que una variable local sea global utilizando la keyword global delante de una variable.

Si habéis entendido bien todo esto deberías poder saber que número devuelve el siguiente código. Si tenéis dudas o no estáis seguros muy seguros, dejad un comentario.

x = 12
def g(x):
   x = x + 1
   def h(y):
      return x + y
   return h(6)
print(g(x))

Podéis leer mucho más sobre el scope y la vida de las variables en este detallado documento (en inglés) escrito por la Universidad de Cape Town.

Pasemos ahora a otro ejemplo muy interesante de programación recursiva en el que, en la propia definición de una función, llamamos no una, sino dos veces a la misma función que estamos definiendo. Además, aquí voy a escribir las dos versiones: la función iterativa y la función recursiva. La idea es escribir una función que devuelva el n-ésimo número de la sucesión de Fibonacci. Podéis leer en detalle sobre esta sucesión en la entrada de la Wikipedia, pero lo único que necesitáis saber es que los dos primeros elementos de la sucesión son 1 y los sucesivos elementos se obtienen sumando los valores de los dos elementos anteriores.

def fib_iter(n):
   fib = [1,1]
   while n > 2:
      fib.append(fib[-1]+fib[-2])
      n -= 1
   return fib[-1]


def fib_recur(n):
   if n == 0 or n == 1:
      return 1
   else:
      return fib_recur(n - 1) + fib_recur(n - 2)

Este ejemplo es perfecto para ver dos cosas. En primer lugar, que la programación recursiva es más fácil de leer, no hay bucles, ni tampoco tenemos que estar atentos a un contador y decidir cuándo salir del bucle, siempre en cuando hayamos definido bien los casos base, en este caso cuando n vale 0 o 1. En segundo lugar, que la programación recursiva puede ser tremendamente ineficiente si no tenemos cuidado. Si probáis a llamar a las dos funciones con valores pequeños de n no notaréis diferencias. Pero probad a ejecutar fib_recur(35). ¿Por qué tarda tanto mientras que fib_iter(35), por el contrario, parece instantáneo? Pues la diferencia es que el código iterativo recorrió el bucle 34 veces mientras que el código recursivo llamó a la función en 14930352 ocasiones. ¿A qué se debe esta ineficiencia? A que estamos calculando una y otra vez valores de la sucesión de Fibonacci que ya habíamos calculado previamente. En el siguiente diagrama marco en rojo los valores que estamos volviendo a calcular para el sencillo caso en el que n vale 5.

Como podéis ver, para computar fib_recur(5) necesitamos fib_recur(4) y fib_recur(3). A su vez, para fib_recur(3) necesitamos fib_recur(2) y fib_recur(1). Etcétera, etcétera. Una vez conocemos fib_recur(4), no necesitaríamos nada más para obtener fib_recur(3) porque ya lo hemos calculado en pasos anteriores. Sin embargo, debido al modo en que hemos escrito la función, se volverán a calcular todos los elementos de la sucesión. En general, esto se soluciona implementado algún tipo de “memoria” a la función de forma que pueda recuperar resultados previos ya computados. En Python podemos hacer uso de los diccionarios. La función recursiva, ahora mucho más eficiente haciendo uso de un diccionario para recuperar cálculos previos, quedaría así:

def fib_recur(n, memoria={1:1, 2:1}):
   try:
      return memoria[n]
   except KeyError:
      memoria[n] = fib_recur(n-1) + fib_recur(n-2)
      return memoria[n]

Los casos base ahora están guardados en el diccionario en la variable memoria. Cuando se llama a la función, lo primero que intenta hacer es devolver el valor alojado en el diccionario. Si este elemento de la sucesión no ha sido calculado, la pareja clave:valor no existirá y entonces se ejecutará el código encerrado dentro del except. Aquí recuperamos el código anterior, salvo que ahora, en vez de devolverlo directamente, primero añadimos una pareja nueva al diccionario memoria. Con este algoritmo estamos evitando todas las casillas rojas del diagrama ineficiente anterior.

¿Aún con dudas? ¿Te sientes igual de confuso que Robert Fischer en Inception? Tranquilo, como en todo, hay que acostumbrarse a esta nueva forma de pensar. Puedes leer más sobre programación recursiva en Python, con muchos más ejemplos y ejercicios planteados en uno de los capítulos del libro Python Practice Book de Anand Chitipothu. También es muy interesante el capítulo dedicado a ello en el libro How to Think Like a Computer Scientist, donde se pone especial énfasis en la generación de fractales utilizando técnicas de programación recursiva.

Por cierto, la imagen al principio de la entrada la generé utilizando uno de los curiosos “poemas” sobre recursión desarrollado por Greg Tatum y liberado bajo la licencia GPL v3. Podéis ver el código y probarlo en su página de github.