¿Qué es la recursión? Y cuando aplicar recursividad en tus programas

Programar implica abrir tu mente a una nueva forma de pensar. Esto incluye asimilar conceptos que, en otro contexto, pueden parecer abstractos. Uno de los conceptos que más dolores de cabeza suele dar a los estudiantes de programación es el de la Recursividad o Recursión.

A pesar de lo anterior, el uso de recursión no deja de ser una técnica más al momento de escribir código, y puede volverse tremendamente útil para mejorar tu forma de escribir código. A continuación te muestro que es la recursión y como utilizarla en tus programas sin perderte en el camino.

Nota: Todos los ejemplos mostrados utilizan Python 3, sin embargo, la recursión es una propiedad de todos los lenguajes de programación, y los ejemplos pueden ser fácilmente portados al lenguaje de tu preferencia.

¿Qué es la Recursión?

En programación, la recursión, también conocida como recursividad o recurrencia, es un concepto abstracto que hace referencia a que una función o método se invoque a sí mismo dentro del bloque de código que lo define. Para que quede más claro, puedes ver el siguiente fragmento de código que hace uso de recursión:

def contador(n):
    if n>0:
        print (n)
        return contador(n-1)

En el código anterior, creamos una función que imprimirá una cantidad n de números de forma regresiva, sin necesidad de utilizar ciclos while o for.

Lo que ocurre al invocar la función con un argumento de, por ejemplo, 3, es que se comprobará que 3 es mayor a 0, imprimirá el número y después volverá a iniciar la función con el argumento 3-1, como 2 es mayor a 0 volverá a imprimir el número e invocará la función con 2-1 como argumento, se repite el procedimiento. El caso base, o último llamado de la función recursiva será 1-1, como 0 no es mayor a 0, la función terminará.

Lo anterior queda explicado de forma visual en el siguiente diagrama:

Un punto clave del uso de la recursión es el de contar con un caso base que marque el final de las llamadas a la función, de otra forma, terminarás con un ciclo infinito de llamadas recursivas que forzarán el cierre del programa. En la función anterior, se llega al final de la recursividad cuando n es igual o menor a 0.

Ahora que sabemos como avanza la recursión, hay que mencionar otra propiedad: El “retroceso” de los valores una vez se llega al caso base, o al último llamado de recursión. Por ejemplo, consideremos el siguiente programa para obtener el factorial de un número:

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

Factorial

En el código anterior definimos una función factorial que recibe un número n. Si n es mayor a 0, se regresa n multiplicado por la misma función factorial con n-1 como argumento. Si n no es mayor a 0, la función regresa el entero 1 . Este código se aprovecha de los valores que retorna cada llamado a la recursión para obtener el resultado deseado, como se ve a continuación.

¿Cuándo usar recursión en nuestros programas?

A pesar de que puede llegar a ser una técnica muy elegante al momento de programar, la recursión no es la mejor opción en términos de rendimiento, pues implica ejecutar la misma función por cada iteración del problema, teniendose que evaluar de nuevo todos los pasos de la función.

Al momento de ejecutar la función contador que ya mencionamos, se puede representar su complejidad así:

La función contador hace un sólo llamado a la recursividad a la vez, por lo tanto, es una función de complejidad lineal.

Aunque en el caso de funciones con dos llamados a la recursión, la complejidad de la función se dispara. Por ejemplo, en el siguiente código para resolver series de Fibonacci:

def fibo(n):
    if n<=0:
        return 1
    return (fibo(n-1) + fibo(n-2))

Como se realizan dos llamados a la función cada vez que se invoca, la cantidad de operaciones realizadas por la función aumentaría de la siguiente forma:

Como se realiza más de un llamado a la función recursiva, la complejidad de la función es exponencial, pues la cantidad de operaciones realizadas crece exponencialmente con cada iteración.

Y mientras más grande sea el número n, más dificil será representar la complejidad de la función débido a la gran cantidad de operaciones realizadas.

Es decir, cuando usamos recursión en programación, la complejidad crece de forma exponencial en relación a la cantidad de llamados recursivos que hagamos.

Ahora probablemente te preguntes, si la recursión requiere realizar tantas operaciones, entonces ¿Por qué usarla en nuestros programas? La respuesta es: Por legibilidad. Existen problemas que, planteados de forma recursiva, son mucho más sencillos de resolver que si pensamos en ellos como bucles.

Un ejemplo simple es la anterior serie de Fibonacci, que si intentamos resolverla con ciclos nos quedaría algo así:

def fibonacci(n):
    a = 0
    b = 1
    for i in range(0, n):
        temp = a
        a = b
        b = temp + b
    return a

Como puedes ver, se requieren 7 líneas de código para simular lo que usando recursión necesita 3 líneas, además, las que implementan la recursión permiten comprender más rápido el comportamiento de la función.

Entonces, a pesar de la perdida de rendimiento que pueda presentar la recursividad, es muy recomendable usarla para resolver problemas sencillos que implicarían escribir código más complejo si se resuelven de otra forma, al ser usada la recursión en problemas sencillos y en ocasiones puntuales, el impacto en el rendimiento del programa será muy poco.

Recursividad vs Ciclos repetitivos

Cuando comprendemos como utilizar la recursión en nuestros programas, es comun que se compare con el uso de bucles; a fin de cuentas, la utilidad de ambos es resolver problemas repetitivos con variaciones de datos. Sin embargo, no son exclusivos entre sí y cada uno tiene su momento para ser implementado.

Como ya mencioné anteriormente, la recursión gana mucho en legibilidad pero pierde igualmente en rendimiento, por lo que sólo es recomendable para resolver problemas que no requieran de muchos calculos por parte del procesador, mientras que los bucles o ciclos administran de forma mucho más eficiente los recursos de la computadora.

Al momento de representar el rendimiento de cada algoritmo de programación, es bueno utilizar la notación asintótica para tener una idea de la complejidad de cada función. En el caso de la recursión, como por cada invocación a la función es necesario repetir todas las operaciones, se puede decir que su complejidad es de O(c^n), mientras que los ciclos repetitivos se ejecutan de forma líneal, por lo que su complejidad es de O(n). Algo importante sobre los bucles es que su complejidad va en aumento según la cantidad de veces que son utilizados (O(m*n)) y a la cantidad de bucles anidados que contengan ( O(n^c) )

En la siguiente tabla puedes ver representado lo anterior:

La cantidad de operaciones realizadas por una función recursiva crece mucho más rápidamente que las realizadas por un ciclo repetitivo mientras más grande sea el problema.

Conclusión

El Triangulo de Sierpinski es una figura que nos permite apreciar como funciona la recursión visualmente.

La recursividad es una herramienta más, que bien empleada, mejorará la calidad de nuestro código y permitirá a otros (y a nosotros mismos) entenderlo mejor y darle mantenimiento en un futuro, sin embargo, dado su impacto en el rendimiento de los programas, debe usarse a discresión y sin abusar de esta, utilizando ciclos repetitivos cuando sea necesario. Si quieres mejorar tus habilidades en programación, te recomiendo echar un vistazo a la sección del blog dedicada a eso y leer código de otras personas en Github o plataformas similares para conocer diversas técnicas utilizadas para resolver un problema.