Entender las funciones recursivas en Python

Como programador profesional, debes dominar a la perfección los conceptos básicos como variables, sentencias condicionales, tipos de datos, especificadores de acceso, llamadas a funciones, ámbitos, etc. Da igual el tipo de programa que escribas —ya sea para un middleware, desarrollo web o ciencia de datos—: estos son algunos de los fundamentos que necesitas conocer a fondo. Antes que científico de datos, desarrollador web o ingeniero de machine learning, eres programador.

Uno de esos conceptos fundamentales es la recursión, y es clave entenderlo cuando escribes funciones de cierto tipo. Seguramente ya sepas que: "Hay recursión cuando una función se llama a sí misma". Pero ¿qué pasa por debajo? ¿Cómo afecta la recursión a la memoria física? ¿Se puede convertir cualquier función en una función recursiva? En este tutorial encontrarás respuesta a estas preguntas básicas.

Anatomía de una función recursiva:

Puede que ya te hayas encontrado con el término recursión en tus estudios de Informática o de Tecnologías de la Información. En esta sección, vas a repasar esos conceptos de una forma amena. Vamos a ello.

Volvamos a la definición de recursión: "Hay recursión cuando una función se llama a sí misma". Veamos un ejemplo para ilustrarla:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

Puedes ver que la función A() se llama a sí misma. Este es un ejemplo de recursión, y A() es una función recursiva.

Veamos ahora algunas bases de una función recursiva.

Fundamentos de una función recursiva:

Una función recursiva debe cumplir estas dos propiedades:

• Una relación de recurrencia
• Una condición de terminación

Vuelve al fragmento de código anterior para entender estos puntos. Claramente, la función sigue una relación de recurrencia específica:

$n\le 1$ es la condición de parada / condición ancla / caso base, y si se cumple, la recursión se detiene. Es imprescindible especificar esta condición. De lo contrario, la función entrará en un bucle infinito.

(Ten en cuenta que el fragmento de arriba no sigue ningún lenguaje de programación concreto. El objetivo es mostrar un ejemplo de función recursiva.)

Quizá te preguntes por qué alguien escribiría una función recursiva si hay alternativas mejores. Sí, a veces cuesta seguir el rastro de una recursión, pero con práctica verás que la recursión es elegante en términos de legibilidad y variables. La recursión no necesita variables extra para ejecutarse, pero sí una condición de terminación adecuada para parar. A menudo es difícil encontrar esa condición. De nuevo, "la práctica hace al maestro". Más adelante en el tutorial verás cómo un programa puede ser más bonito y conciso si se implementa con recursión frente a medios convencionales. Ahora, pasemos a estudiar la representación en memoria de una función recursiva.

Representación en memoria de una función recursiva:

En esta sección, vas a ver cómo se representan las funciones recursivas en memoria de forma fundamental mediante árboles y pilas. Considera la siguiente función recursiva A() para entenderlo:

void A(n){
    if(n>=1){
        A(n-1);
        print(n);
    }
}

Primero entenderás la representación en memoria usando árboles. Puede sonar complicado, pero es muy directo. Si escribieras cada llamada de función con forma de árbol, ¿cómo quedaría?

Algo como esto:

Un par de puntos a destacar:

• La función se llama con A(3) y, para ello, se realizan 4 llamadas (3+1). Generalizando: si se llama a A(n), en total harán falta (n+1) llamadas a función.
• Las llamadas P() son las impresiones producidas por print(n).
• La función se detiene con la llamada A(0) porque la sentencia if (tras la llamada A(0)) recibe n < 1, lo que hace que la función termine.

Has visto primero esta representación en árbol porque la necesitarás para representar una función recursiva en una pila. Vamos a verlo.

(Una pila es una estructura de datos que sigue el orden último en entrar, primero en salir —LIFO—)

Para la representación con pila, tendrás que recorrer el árbol de arriba abajo y de izquierda a derecha. La siguiente imagen lo aclara.

Interpretando este árbol tan peculiar: recuerda que una pila tiene dos operaciones: 1) Push, con la que insertas un elemento en la pila, y 2) Pop, con la que extraes un elemento de la pila.

Ahora, empieza el recorrido del árbol de arriba abajo y de izquierda a derecha:

• Siempre que veas una llamada a función, haz push en la pila.
• Si ves una llamada a print()/P(), simplemente imprime el elemento correspondiente.

Estos serán los elementos de la pila como resultado del recorrido del árbol desde A(3) hasta A(0) únicamente en el sentido de arriba abajo:

Ahora comienza la segunda mitad del recorrido, es decir, el orden izquierda-derecha. Cada vez que veas una llamada a función por segunda vez, haz pop. Curiosamente, el primer elemento de la pila que saldrá (A(0)) fue el último en entrar (¿recuerdas LIFO?). En tu camino aparecerán tres llamadas P(): P(1), P(2) y P(3). Las imprimirás según vayan apareciendo en el recorrido. El orden será:

Al terminar el proceso de recorrido, la pila quedará completamente vacía. Para entender aún mejor la operación de extracción (pop), aquí tienes una imagen de la pila tras vaciarse por completo.

Has visto cómo representar una función recursiva simple en memoria usando un árbol y una pila. Ahora, verás cómo trazar una recursión.

Trazado de una recursión:

En esta sección, aprenderás a trazar una recursión de forma metódica. Considera la siguiente función recursiva:

void A(n){
    if(n>0){
        print(n-1);
        A(n-1);
    }
}

Un punto crucial: siempre que se llama a una función se crea en memoria un registro de activación que contiene las variables locales de esa función y un puntero de instrucción (que indica la siguiente operación a ejecutar cuando el control vuelva a esa función). Supón que una función llamada main() invoca A() como A(3). Numeremos las líneas de A() desde el if para entenderlo mejor:

void A(n){
    1. if(n>0)
    2. {
        3. print(n-1);
        4. A(n-1);
    5. }
}

Los registros de activación se verían así:

Como se mencionó, las funciones tienen sus propias copias de las variables locales y los punteros de instrucción (en este caso, el número de línea). Tras A(0) la función A() terminará y comenzarán las extracciones de la pila. Observa que aquí se usa una pila horizontal, que es exactamente la misma que ya viste en el tutorial. Mientras los registros se apilan, también se realizan las impresiones y se mostrarán los siguientes elementos:

Los punteros de instrucción son vitales aquí porque a menudo, en una función recursiva, el control vuelve a la misma función pero con un valor de variable distinto. Para mantener todo sincronizado, estos punteros ayudan muchísimo. Puedes seguir este mismo proceso para trazar una recursión usando una representación en árbol.

Ahora vas a estudiar cómo realizar un análisis espacio-tiempo de una función recursiva.

Análisis espacio-tiempo de una función recursiva:

DataCamp tiene un artículo excelente sobre análisis asintótico en Python, y es recomendable que le eches un vistazo antes de leer esta sección. Repasemos rápidamente qué significan los análisis de espacio y tiempo de una función (también conocidos como complejidad espacial y complejidad temporal):

Para una entrada dada, una función debe producir algún tipo de salida. Para hacerlo, ¿cuánto tiempo tarda? La complejidad temporal aproxima ese tiempo y también se llama tiempo de ejecución de la función. De forma similar, la complejidad espacial aproxima los requisitos de espacio (memoria) de una función para una entrada dada. Pero, ¿por qué hacen falta estos análisis?

• En lugar de ejecutar una función con entradas de distintos tamaños, puedes aproximar fácilmente cómo se comportará con tamaños variables.
• Si tienes dos funciones que cumplen el mismo objetivo, ¿con cuál te quedas? ¿Qué medidas considerarías para decidir? Exacto: las comparas analizando sus complejidades de espacio y tiempo y ves cuál rinde mejor.

Tomemos ahora una función recursiva sencilla y analicemos su complejidad de espacio y tiempo.

void A(n){
    if(n>1) // Anchor condition
    {
       return A(n-1);
    }
}

Empecemos por la complejidad temporal. Supón que el tiempo total que tarda la función A() es $T(n)$. Ahora, $T(n)$ es la suma del tiempo de comparar si n es mayor que 1 y el tiempo de ejecutar A(n-1). Así, $T(n)$ puede expresarse como:

1 es el tiempo de la comparación (puedes poner cualquier constante). Ahora, ¿cuál será el tiempo (en términos de $T(n)$) para ejecutar A(n-1)?

Del mismo modo,

y así sucesivamente.

Si te fijas, todas las ecuaciones están conectadas, ¿verdad? Si las sustituyes una tras otra, obtienes:

$T(n)$ = 1 + (1 + $T(n-2)$) = 2 + $T(n-2)$ = 3 + $T(n-3)$ = .... = k + $T(n-k)$ (tras ejecutar la función durante k términos)

Ahora, debes determinar en qué punto va a parar la función. Según la condición ancla dada, puedes escribir:

Supón que, tras ejecutarse durante k términos, la función se detiene. Si es así, entonces:

$n - k = 1 => k = n - 1$

Ahora, sustituyendo el valor de k (= n - 1) en $T(n) = k + T(n-k)$:

$T(n) = (n-1) + T(n-(n-1))$
$=> T(n) = (n-1) + T(1)$
$=> T(n) = n-1 + 1 = n$ // Para T(1) solo se requiere la comparación

Por la regla del análisis asintótico, $T(n) = n$ puede reescribirse como $T(n) = \mathcal{O}(n)$. Esto significa que la complejidad temporal (en el peor caso) de la función es $\mathcal{O}(n)$.

Quizá quieras ir más despacio y observar cada paso con atención. Te recomendamos hacerlo con papel y bolígrafo para interiorizar cada detalle.

El análisis de complejidad espacial de la función es sencillo. La función trabaja en memoria y no usa variables adicionales. Por tanto, puedes concluir que la complejidad espacial de la función es $\mathcal{O}(n)$.

Ahora vas a juntar todo esto e implementar una función recursiva simple en Python.

Implementar una función recursiva simple en Python:

Vas a escribir una función recursiva para calcular el factorial de un número dado. Después, crearás una versión iterativa de la misma función. Vamos a ello.

# Recursive function factorial_recursion()

def factorial_recursion(n):  
   if n == 1:  
       return n  
   else:  
       return n*factorial_recursion(n-1)

# Call the function

num = 7
print("The factorial of ",num," is ",factorial_recursion(num))

The factorial of  7  is  5040

¿Recuerdas los dos ingredientes clave de una función recursiva?

• Relación de recurrencia
• Condición de terminación

En este caso, la relación de recurrencia puede ser:

$f(n) = n!$
$f(n) = n * f(n-1)$ y así sucesivamente.

La condición de terminación es cuando n es igual a 1.

Fácil, ¿verdad?

Ahora, implementa la versión iterativa de la misma función.

def factorial_iterative(num):
    factorial = 1
    if num < 0:
        print("Sorry, factorial does not exist for negative numbers")
    elif num == 0:
        print("The factorial of 0 is 1")
    else:
        for i in range(1,num + 1):
           factorial = factorial*i
        print("The factorial of",num,"is",factorial)

factorial_iterative(7)

The factorial of 7 is 5040

La diferencia entre ambas versiones salta a la vista. La versión recursiva es mucho más elegante que la iterativa, ¿no crees?

¡Enhorabuena!

Has llegado hasta el final. En este tutorial, has estudiado a fondo las funciones recursivas. Desde lo más básico hasta el análisis de complejidad espacial y temporal de una función recursiva: lo has cubierto todo. También has visto cómo la recursión puede ser ventajosa para resolver problemas con ciertas características. Ahora deberías estar en condiciones de resolver problemas (que tengan una relación de recurrencia y una condición de parada) usando recursión. Por ejemplo, puedes intentar calcular los números de Fibonacci dentro de un rango usando recursión.

Te animo a resolver problemas clásicos como búsqueda binaria, ordenación por mezcla (Merge Sort), las Torres de Hanói, etc., usando recursión y a realizar también el análisis espacio-tiempo. Sin duda, esto te hará mejor programador.

Como introducción, lo visto es suficiente. Pero si quieres profundizar más en recursión, visita estos enlaces:

• Recursion and Dictionaries, por el Prof. Grimson
• Programación dinámica para optimizar el rendimiento de funciones recursivas

Si quieres aprender más sobre Python, haz el curso gratuito de DataCamp Intro to Python for Data Science.