Otras yerbas, Euclides, Python y la recursividad

Recurrencia, recursión o recursividad. Al principio me parecían palabras casi inentendibles. Sobre todo porque en vez de buscarlas en un diccionario, efectivamente creía que eran imposibles de entender y por lo tanto trataba de olvidarlas. Como verás, con resultados nefastos.

Según la rae, “recurrencia” es la “propiedad de aquellas secuencias en las que cualquier término se puede calcular conociendo los precedentes”.

Propiedad de aquellas secuencias en las que cualquier término se puede calcular conociendo los precedentes. Elemental. Conocer los precedentes implica que debe haber un precedente preexistente. Tal es así, que en las recursividad, primero es el huevo.

Un ejemplo podría ser de más ayuda. Factoriales! Los factoriales (denotados por la adición a un número del caracter_!_), en principio son el producto de todos los números enteros positivos desde 1 (números naturales!) hasta x. De modo tal que: $$4! = 4 x 3 x 2 x 1 ⇒ 4! = 24$$

Y qué tiene que ver esto con la recursividad? Quizás en este momento no puedas verlo, como me pasó a mí en su momento, o nos pasó a todos. Si queremos calcular 4!, recordando la premisa de que la recurrencia es una propiedad de aquellas secuencias en las que cualquier término se puede calcular conociendo los precedentes, podemos empezar por calcular 1!, ya que 2! es igual a 2 x 1!. Éste 1!, vendría a ser nuestra piedra fundacional.

Entonces podemos definir tratar de definir a nuestra función factorial.

1
2
3

def factorial(n):
    if(n == 1):
        return 1

Funcionaría bárbaro para calcular 1!, pero qué sucede con 2!? He aquí el quid de la cuestión. Para llegar a 1 (nuestra piedra fundacional) desde 2, sólo es necesario restarle 1, ya que 2 - 1 = 1 (siempre y cuando hayas avanzado desde la salita de 4 años). Entonces podemos volver a intentar definir nuestra función:

1
2
3
4

def factorial(n):
    if (n == 1):
		return 1
    return n * factorial(n - 1)

Esta nueva función computaría correctamente la respuesta, siempre y cuando no caigamos en la tentación e invoquemos la función con algún número menor a 1. Programar esos casos puede ser un buen ejercicio para el lector (siempre quise decir eso).

Otra gran ejemplo de funciones recursivas es el algoritmo de Euclides para calcular el máximo común divisor o MCD.

1
2
3
4

def MCD(a,b):
	if b == 0:
		return a
	return MCD(b, a % b)

Vale aclarar que la operación que se realiza entre a y b, denotada con un símbolo % devuelve el resto de dividir a por b.

La función MCD se invoca a sí misma hasta que encuentra una pareja de un número entero positivo y 0. Todos sabemos que el MCD(n, 0) = n.

Para vos quizás puede parecer algo súper fácil y creés que este post es súper inútil. Está perfecto. A mí, encontrarme con este tipo de poder, para realizar este tipo de funciones me sigue pareciendo impresionante. Me abrió los ojos y me permitió entender un poco más de Python, un poco más sobre la recursión, un poco más de algoritmos, un poco más de todo.

Y qué es la vida sin seguir aprendiendo?