Recursividad

Factorial

El ejemplo típico para explicar recursividad es el cálculo del factorial de un número (el operador matemático utilizado es "!").

El factorial de un número N es el producto de todos los números enteros desde 1 hasta N.

Ejemplo:

• !5 = 1 * 2 * 3 * 4 * 5

Lo interesante acá es ver que factorial de 4 es:

• !4 = 1 * 2 * 3 * 4

Como vemos !5 contiene en su solución a la solución de !4. Agregándole la multiplicación por el 5. Y así sucederá para cualquier N.

• !5 = 1 * 2 * 3 * 4 * 5
• !5 = !4 * 5

Entonces, ahí encontramos una manera de expresar la solución en forma recursiva. Podemos plantear los casos generales para todo N:

• Caso base: 0! = 1
• Regla recursiva: n! = n * (n-1)!

Esto significa que si quiero calcular el factorial de 5, se debe ir resolviendo los siguientes pasos:

1. 5! Lo solicitado
2. 5 * 4! al aplicar la regla recursiva
3. 5 * 4 * 3! al aplicar la regla recursiva
4. 5 * 4 * 3 * 2! al aplicar la regla recursiva
5. 5 * 4 * 3 * 2* 1! al aplicar la regla recursiva
6. 5 * 4 * 3 * 2* 1 * 0! al aplicar la regla recursiva
7. 5 * 4 * 3* 2* * 1 * 1 al aplicar el caso base
8. 120 el resultado

De esta manera se ve como la regla recursiva se va aplicando hasta que el caso base pone fin a las llamadas recursivas. Es importante entonces definir el caso base ya que si no el cálculo no se puede resolver (quedaría calculando por siempre)

Escribamos nuestro ejemplo en python:

def factorial(n):

    return 1 if n == 0 else  n * factorial(n-1)

y podemos testearlo:

def testFactorial(self):

    self.assertEqual(1, factorial(0))

    self.assertEqual(1, factorial(1))

    self.assertEqual(2, factorial(2))

    self.assertEqual(6, factorial(3))

    self.assertEqual(24, factorial(4))

    self.assertEqual(120, factorial(5))

Acá vemos un diagrama que ayuda a entender la recursividad para el factorial de 5:

Término Fibonacci

Generalmente, las sucesiones matemáticas suelen ser buenos ejemplos para aprender recursión, ya que cada término suele ser formulado en base de un término anterior. Por ejemplo tenemos la sucesión de fibonacci en la cual sabemos dos casos bases (el 0 y el 1) y una regla recursiva para los demás:

S(0) = 0

S(1) = 1

S(n) = S(n-1) + S(n-2)

y una implementación posible en python es:

def terminoFibonacci(termino):

    return 0 if termino == 0 else 1 if termino == 1 else terminoFibonacci(termino - 1) + terminoFibonacci(termino - 2)

y su test:

def testTerminoFibonacci(self):

    self.assertEqual(0,terminoFibonacci(0))

    self.assertEqual(1,terminoFibonacci(1))

    self.assertEqual(1,terminoFibonacci(2))

    self.assertEqual(2,terminoFibonacci(3))

    self.assertEqual(3,terminoFibonacci(4))

    self.assertEqual(5,terminoFibonacci(5))

    self.assertEqual(8,terminoFibonacci(6))

    self.assertEqual(13,terminoFibonacci(7)) 

Manejando Listas recursivamente

Muchas veces es conveniente ver a las listas como la unión de un elemento (cabeza o head) y otra lista (cola o tail). Esta es una definición recursiva (el caso base es la lista de un elemento solo, que se compone de la cabeza y la lista vacía). Esta definición sirve para resolver un gran número de problemas de manera recursiva.

Acá van un grafiquito que puede ayudar a entender cómo ver las listas de esta nueva manera:

Como vemos, la lista "l1" se puede pensar como:

• el número 1 + otraLista (llamémosla L2)
• L2 = 2 + L3
• L3 = 3 + LISTA_VACIA

Ven que se parece a la idea del factorial. Yo podría así expresar cálculos pequeños como "pasos" que solo operan con un elemento, y llaman a la función nuevamente con la cola de la lista.

Acá va otro dibujito simpático para representar lo mismo:

Veamos algunos ejemplos:

Primero, un par de funciones que nos ayudan a expresar las listas en cabeza/cola

def cabeza(lista):

    return lista[0]

def cola(lista):

    return lista[1:] 

Calcular el máximo de una lista

• Caso Base: El máximo de una lista que tiene un sólo elemento es ese elemento
• Regla Recursiva: El máximo de una lista es el mayor valor entre la cabeza y el máximo de su cola

def maximo(lista):

    #caso base

    if (len(lista) == 1):

        return cabeza(lista)

    #caso recursivo

    head = cabeza(lista) 

    maximoTail = maximo(cola(lista))

    return head if head > maximoTail else maximoTail

Y su test sería:

  def testMaximo(self):

        self.assertEquals(23, maximo([4,5,7,1,2,23,16]))

        self.assertEquals(32, maximo([4,5,7,1,2,23,16,32]))

        self.assertEquals(54, maximo([54,4,5,7,1,2,23,16,32]))

        self.assertEquals(5,maximo([5]))

Calcular la sumatoria

• La sumatoria de una lista vacia es 0 (caso base)
• La sumatoria de una lista es la cabeza más la sumatoria de la cola (regla recursiva)

def sumatoria(lista):

#caso base

if (len(lista) == 0):

return 0

#caso recursivo

return cabeza(lista) + sumatoria(cola(lista))

Y el test:

  def testSumatoria(self):

        self.assertEquals(20, sumatoria([3,5,4,8]))

        self.assertEquals(8, sumatoria([3,5]))

Método reducir (reduce)

• La reducción de una lista de un elementos es ese elemento (caso base)
• La reducción de una lista es aplicar la función reductora a la cabeza y al resultado de recudir la cola (caso recursivo)

def reducir(lista, funcion):

    #Caso base

    if (len(lista) == 1):

        return lista[0]

    #Caso recursivo

    return funcion(cabeza(lista), reducir(cola(lista),funcion))    

Test:

    def testReducir(self):

        self.assertEquals(20, reducir([3,5,4,8], lambda x, y: x + y))

        self.assertEquals(8, reducir([3,5], lambda x, y: x + y))

Método mapear

El método mapear es levemente más complejo que los anteriores porque necesitamos ir generando una lista a medida que ejecutamos los casos recursivos. Sin embargo aplica los mismos principios: si encuentro un buen caso base y una regla recursiva, el problema se resuelve:

• el map de una lista vacia es otra lista vacia (Caso Base)
• el map de una lista es otra lista que se forma al concatenar el resultado de aplicar la funcion a la cabeza junto con la lista mapeada de la cola

def mapear(lista, funcion):

    #caso base

    if (len(lista)== 0):

        return []     

    #regla recursiva

    return [funcion(cabeza(lista))] + mapear(cola(lista), funcion)

Su respectivo test:

    def testMapear(self):

        self.assertEquals([2], mapear([1], lambda x: 2 * x))

        self.assertEquals([2,4,6], mapear([1,2,3], lambda x: 2 *x))

Semillas

Si bien ya vimos la mecánica principal de la idea de recursividad todavía hay una variante muy utilizada, ya que es necesaria para resolver ciertos problemas o bien para resolverlos de forma "eficiente". Esto es el uso de "semillas"

Una semilla es una variable que comienza con un valor inicial al comenzar la invocación recursiva (de ahí el término semilla) y se va modificando a medida que se producen las llamadas anidadas. Es una técnica útil para ir arrastrando información durante todo el proceso recursivo.

Veamos dos ejemplos:

Mapear con semilla

Un poco más arriba vimos ya cómo implementar la función mapear (así como también la filtrar y reducir) en forma recursiva. Eso que hicimos está muy bien. Sin embargo, quizás alguno habrá nota ya que no parece ser muy eficiente. Porque, por un lado al utilizar recursividad estamos básicamente aplicando la idea de dividir y conquistar, reduciendo un problema donde procesábamos muuuuuchos elementos, a expresarlo en términos de procesar uno, y luego recursivamente al resto.

El problema con esto es que al dividir el cálculo, luego eventualmente hay que volver a juntar todos los resultados. Y esto se hace en cada llamada.

Por ejemplo, en el map, habrán notado que al mapear cada elemento se genera una nueva lista con el su resultado más el resultado de mapear la cola que involucrará más listas según cuántos elementos tenga. Entonces nuestra función si bien retorna una lista, para calcularla/crearla tuvo que crear muchas en el proceso. Eso no suena muy eficiente.

Entonces, una forma de evitar esto es utilizando semillas, que como decíamos antes es una forma de compartir estado de la ejecución completa de la llamada recursiva entre cada uno de los pasos.

En este caso nuestra semilla será una lista inicialmente vacía donde se iran agregando los tranformados por la función map.

• Al mapear una lista vacía no hay que hacer nada
• El map de una lista es agregar a la lista de resultados lo que se obtiene de aplicar la función a la cabeza y luego mapear la cola

def mapearConSemilla(lista, funcion):

    #manejo la semilla

    resultado = []

    subMapearConSemilla(lista, funcion, resultado)

    return resultado

def subMapearConSemilla(lista, funcion, listaResultado):

    #caso base

    if (len(lista)== 0):

        return 

    #caso recursivbo

    listaResultado.append(funcion(cabeza(lista)))

    subMapearConSemilla(cola(lista), funcion, listaResultado)

Como se ve acá, al utilizar semillas necesitamos ahora partir el problema en dos funciones. La inicial que es la llamada por el "usuario", que no recibe la semilla, ya que siempre tendría que pasarnos una lista vacía de otra forma. Y luego, internamente ésta invoco al verdadero mapear que utiliza semilla, el subMapearConSemilla que tiene la recursividad.

Fibonacci

Pensemos ahora si en lugar de querer obtener un término de la sucesión, queremos todos los términos (hasta un término que se le da por parámetro, para evitar el cálculo hasta el infinito). Pensemos en el test primero, para darnos una mejor idea de lo que pretendemos:

def testFibonacci(self):

    self.assertEqual([0,1,1,2,3,5,8,13], fibonacci(8))

Una manera de solucionarse es resolverlo sin recursividad con las listas por comprensión:

def fibonacci(hasta):

    return [terminoFibonacci(n) for n in range(hasta)]

Pero también puede solucionarse de forma recursiva, es decir, que en cada llamada recursiva se pueda calcular un término. Para esto hay que tener presente algunas cuestiones. Al igual que en la forma anterior, vamos a reutilizar la función que calcula cada término, pera para eso es necesario saber que término se está calculando: la primera vez que llamamos calculamos el término 0, la segunda vez el término 1, la tercera el 2, así hasta llegar al término recibido por parámetro. Esto nos lleva a la idea de que en cada llamada recursiva necesitamos saber algo sobre la ejecución anterior.

Entonces, cómo vimos ya según la definición, podríamos utilizar la semilla para contar la cantidad de veces que estamos invocando la función.

Nuestra definición recursiva tendrá en cuenta la semilla (que en nuestro caso representa al término actual que se está calculando) y además como vamos a devolver una lista, nuestros casos base y recursivo expresarán la construcción listas (con la misma técnica que usamos en el map en la sección anterior)

Nuestra definición recursiva es:

• Si el términoActual llegó al hasta, devolvemos la lista vacía (Caso base)
• La sucesuón de fibonacci es la lista resultante de concatenar el el término de fiboncacci actual y el cálculo de la suceción hasta llegar al término deseado

#el valor inicial de la semilla (termino actual) es 0

def fibonacciRecursivo(hasta, terminoActual= 0):

    #el caso base

    if (hasta == terminoActual): 

        return [] 

    #el caso recursivo

    return [terminoFibonacci(terminoActual)] + fibonacciRecursivo(hasta, terminoActual + 1)

def testFibonacciRecursivo(self):

        self.assertEqual([0,1,1,2,3,5,8,13], fibonacciRecursivo(8))       

Usando semillas como alternativa al valor de retorno

No siempre que necesitemos generar una lista en forma recursiva estamos obligados a ir concatenando valores en la devolución de resultados. Otra alternativa es usar el concepto de semilla para simplificar esa operación final. La idea es generar una lista vacía inicial, que es modificada por cada llamada recursiva. Al finalizar las llamadas recursivas el resultado queda en esta lista. Tal cual como vimos para el mapear con semilla.

Al modificar la solución de la sucesión de fibonacci para mostrar esta alternativa se hace evidente que necesitamos separar la función en 2: una que es la invocada por nuestro usuario y determina los valores iniciales de las semillas, y otra que es la que realiza las llamadas recursivas:

def fibonacciResultadoComoSemilla(hasta):

    #Define las semillas

    terminoActual = 0

    lista = []

    #Invoca por primera vez a la funcion recursiva

    subFibonacciResultadoComoSemilla(hasta, terminoActual, lista)

    #el resultado queda en la lista

    return lista

def subFibonacciResultadoComoSemilla(hasta, terminoActual, lista):

    #el caso base, cuando el terminoActual llega al hasta

    if (hasta == terminoActual): 

        return 

    #modificamos la lista que vamos a usar como valor de retorno

    lista.append(terminoFibonacci(terminoActual))

    #realizamos la siguiente invocacion recursiva

    #pero con el termino actual y la lista modificada 

    subFibonacciResultadoComoSemilla(hasta, terminoActual + 1, lista)

def testFibonacciResultadoComoSemilla(self):

    self.assertEqual([0,1,1,2,3,5,8,13], fibonacciResultadoComoSemilla(8))   

Tail Recursion

//TODO: explicar con el ejemplo de factorial

Código fuente:

• Todo el código fuente está en el paquete "recursividad" en diferentes archivitos acá
• test sobre recursividad

Ejercicios

En la sección de Ejercicios y Trabajos Prácticos podrán encontrar más ejemplos y ejercicios de recursividad.

Referencias y Links

• http://www.codeproject.com/Articles/25470/Recursion-Primer-Using-C-Part-1