La Recursividad: Paso a Paso

 

Si has visto nuestro artículo anterior referido a la recursividad, probablemente estés ansioso/a por empezar a implementar sus conceptos para terminar de comprenderlos. Si aún no lo has visto, te recomiendo leer la introducción primero, en este artículo.

El día de hoy, te presentaré un típico ejemplo de recursividad, y analizaremos paso a paso cómo Python resuelve este tipo de problemas, cuál es la lógica detrás de un problema de carácter recursivo, y nos introduciremos en cómo se gestiona la memoria en estos casos. Desarrollaremos el famoso caso del factorial.

Traigamos a memoria antes de empezar, el concepto de recursividad: es la forma en la cual se especifica un proceso basado en su propia definición, o un problema cuyos pasos intermedios pueden resolverse con los mismos pasos que los del proceso general.

Por otro lado, también necesitaremos echar mano del concepto de factorial que, para un número cualquiera n, es el producto de todos los números enteros positivos desde 1 hasta n. Por ejemplo, el factorial de 3 es igual al producto de 3 x 2 x 1. Por supuesto, las cosas comenzarán a complicarse cuanto mayor sea el número n, ya que se irán incorporando mayor cantidad de factores.

Vamos ahora de lleno a desarrollar un problema factorial de manera recursiva. Para ello, definimos una función llamada factorial, donde recordando los requisitos de la recursividad, necesitaremos lo siguiente:

1. Un caso base: aquel que de alcanzado, debe interrumpir la recursión, evitando que el problema se ejecute infinitamente.
2. La invocación de la función por la propia función, tal que el siguiente paso pueda resolverse aplicando los mismos pasos del problema general. Es decir, llegaremos a un punto en que la función factorial, deba invocar a la función factorial.
3. Para darle un sentido de progreso, necesitaremos que esta siguiente invocación, haga evolucionar el proceso pasando como argumento un valor diferente al original. Esto también ayudará a impedir que caigamos en una recursión infinita.

Ahora bien, tomando en cuenta lo anterior, analicemos la función factorial desarrollada de manera recursiva:

1	def factorial(x):
2	if x == 1:
3	return 1
4
5	return x * factorial(x-1)

Vemos que tenemos todos los requisitos anteriores, aquí con mayor detalle:

El caso base es cuando se busca el factorial del número 1. El motivo es sencillo y surge de la propia definición de factorial, que debe realizar el producto de todos los números positivos entre 1 y n. Si n = 1, entonces el problema se extingue en ese mismo paso, y no hay motivos para continuar explorando otros números.

Para el caso en que el número entregado por el argumento sea un número mayor que 1, digamos por ejemplo factorial(3) para no extendernos demasiado, entonces comienza la magia: en la línea 2 se descartará la condición lógica planteada, y la ejecución continuará por la línea 5. Dicha línea ya contiene un return. Alcanzar un return en el contexto de una función implicaría que hemos llegado al final de la misma, ya que es siempre la última linea antes de finalizar la invocación. Sin embargo, aquí está el truco de la recursividad: para poder devolver este return, se necesita resolver el producto de x por ¡la invocación de la función factorial para el siguiente valor de x! Como x es conocido (le habíamos dado el valor 3), para poder resolver el producto necesitaremos resolver primero la función factorial con x - 1 = 3 - 1 = 2. 

Esto genera un nuevo llamado a la función factorial, que ahora se ejecutará como factorial(2). Nos hallamos nuevamente en la línea 1. Avanzamos a la línea 2, donde nuevamente descartamos la condición ya que 2 no es igual a 1, y continuamos por la línea 5. Aquí llegamos nuevamente al return, y otra vez para poder resolverlo, necesitaremos el valor de x (que en esta ejecución equivale a 2), y el resultado de la función factorial con el argumento 2 - 1 = 1. Como nuevamente Python, para poder resolver este return, necesitará resolver primero factorial(1), volveremos a la línea 1.

Al ejecutar factorial(1) sin embargo, ocurrirá algo diferente, ya que conocemos por la línea 2 que hemos llegado al caso base, aquel en el que x == 1. ¡Esto es algo muy bueno! No solo porque avanzamos en la solución correcta, sino porque hemos logrado detener la ejecución infinita, avanzando con pasos lógicos que el problema requiere. Por lo tanto, en este caso la condición base de la línea 2 se valida, y llegamos al return de la línea 3. Este return puede resolverse de maneral trivial: la función devuelve 1 y termina la ejecución de factorial(1).

Que hayamos alcanzado y resuelto un return, desde luego no significa que hayamos finalizado: este return ha resuelto factorial(1), que a su vez es requisito para resolver factorial(2), ya que en la línea 5 teníamos:

5    return 2 * factorial(1)

Por lo que resuelto quedaría:

5    return 2 * 1

Y este resultado (2) será el resultado de factorial(2). A su vez, recuerda que necesitábamos este resultado para poder resolver finalmente el factorial(3), que en la línea:

5    return 3 * factorial(2)

necesitaba contar con el resultado que recién hemos obtenido, y ahora sí pudo resolverse:

5    return 3 * 2

Y con esta ejecución, hemos alcanzado el return de la función factorial(3) que invocamos originalmente, la cual devolverá el valor 6.

Hemos resuelto un caso sencillo, pero aplicando todos los ingredientes de la recursividad. Y por más que cada uno de los pasos haya sido aclarado, puede que te estés preguntando por qué esto tiene realmente sentido, y si hemos llamado a la misma función varias veces, cómo es posible, por ejemplo, que se haya mantenido en memoria lo que aún quedaba por resolver.

Pero ha sido bastante por hoy, así que lo trataremos en el artículo final de Recursividad y Stack. ¡Nos veremos allí!