Clase6_2

Contenido¶

Introducción ¶

Inicialmente, podemos entender como recursión al proceso en que una función se llama a sí misma. Por ejemplo, lo dicho anteriormente se puede ilustrar con la siguiente idea:

def func(. . .):
    # Instrucciones
    # .
    # .
    func(. . .)
    # .
    # .

donde, dentro de las instrucciones de la función func, estamos utilizando propiamente la función func(), esto es, dentro de las instrucciones de la definición de dicha función, estamos mandando a llamar a esa misma función. Tal vez por ahora parezca algo confunso, pero a lo largo de esta clase indagaremos más a detalle sobre qué es la recursión y cómo la podemos implementar en Python.

Respecto a la recursión podemos decir que:

Es un proceso que se define en términos de sí mismo.
Se ocupa para dividir un problema en subproblemas que están relacionados entre sí, de modo que las soluciones a estos subproblemas, de manera global, representan la solución del problema principal.
Podemos pensar a la recursión, al menos de manera intuitiva, como una "especie" de bucle.

Veamos un ejemplo rápido sobre la implementación de una función recursiva:

Lo que hacemos primero es escribir el código de la función recursiva. Notemos que, lo primero que hace esta funcion es ver si el parámetro ingresado es mayor o igual a cero. Si se cumple la condición, entonces imprimimos el valor del parámetro ingresado, después le restamos uno y luego volvemos a llamar de nuevo a la función func que estamos definiendo, y repetimos este proceso hasta que la condición del condicional definido en las instrucciones de la función ya no se cumple, por lo cual se ejecutará el print("fin") del else. De manera más detallada por decir que:

Supongamos que mandamos a llavar a nuestra función ingresando el valor de 3 (así como la imagen de arriba): func(3).
Por medio de nuestra función se ejecutará:

# En este caso x vale 3
    if x >= 0:
        print(x)     # se imprimira en consola el valor de 3
        x -= 1       # ahora x vale dos pues 3-1=2
        func(x)      # mandamos a llamar nuestra funcion de nuevo
                     # pero ahora cuando x vale 2

al nosotros escribir func(x) hacemos que la función se vuelva a ejecutar desde las instrucciones iniciales, de modo que:

# En este caso x vale 2
    if x >= 0:
        print(x)     # se imprimira en consola el valor de 2
        x -= 1       # ahora x vale uno pues 2-1=1
        func(x)      # mandamos a llamar nuestra funcion de nuevo
                     # pero ahora cuando x vale 1

Notemos que, de cierto modo, la recursión de funciones actúa como una especie de bucle. Continuamos:

# En este caso x vale 1
    if x >= 0:
        print(x)     # se imprimira en consola el valor de 1
        x -= 1       # ahora x vale 0 pues 1-1=0
        func(x)      # mandamos a llamar nuestra funcion de nuevo
                     # pero ahora cuando x vale 0

para la siguiente iteración tendremos que

# En este caso x vale 0
    if x >= 0:
        print(x)     # se imprimira en consola el valor de 0
        x -= 1       # ahora x vale menos uno pues 0-1=-1
        func(x)      # mandamos a llamar nuestra funcion de nuevo
                     # pero ahora cuando x vale -1

y finalmente

# En este caso x vale -1
    # La condicion del if ya no se cumple
    if x >= 0:
        print(x)     
        x - = -1
        func(x)
    # Se ejecutara entonces la condicion del else
    else:
        print("Fin")   # se imprimira en consola el mensaje "Fin"

con esta última ejecución tenemos que la ejecución global de nuestra función ha terminado, es decir, todos los procesos realizados que vimos antes corresponden de manera global a la ejecución de func(3). De lo observado podemos ver cómo el "problema", el cual busca solucionar nuestra función func(3), es dividido en varios "subproblemas" (func(2), func(1), func(0), func(-1)), donde la solución a estos "subproblemas" se convierte, de manera global, en la solución del "problema" original. Así, tenemos entonces que la salida de nuestra función será

In [2]:

def func(x) -> None:
    """Función recursiva que recibe un parámetro 
    y no retorna nada. Esta función realiza 
    una cuenta regresiva a partir de un número dado."""
    # Se imprimira x siempre y cuando sea mayor o
    # igual a cero
    if x >= 0:
        print(x)  
        # le iremos restando 1 a la x en cada 
        # "iteracion"
        x -= 1
        # mandamos a llamar a nuestra misma funcion
        # pero con un valor distinto para la x
        func(x)
    # En caso de que nuestro numero no se mayor o
    # igual a cero, imprimiremos un mensaje 
    else:
        print("Fin")   
        
# Probamos nuestra funcion
func(3)

3
2
1
0
Fin

El proceso recursivo anterior lo podemos visualizar mediante el siguiente diagrama

donde podemos ver que el comportamiento es bastante similar al de un bucle.

De tal manera vemos que lo que está realizando nuestra función es una especie de cuenta regresiva hasta llegar a cero, así, como ingresamos el valor de 3 en nuestra función, entonces obtuvimos en salida:

3
2
1
0
Fin

Continuemos abordando más ejemplos sobre recursión.

Factorial de un número ¶

En matemáticas, definimos el factorial de un número $n\in \mathbb{N}$, como el número obtenido de calcular $n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1$, a este número lo solemos denotar por $n!$. Por ejemplo:

$2! = 2\cdot 1 =2$
$3! = 3\cdot 2\cdot 1=6$
$5! = 5\cdot 4\cdot 3\cdot 2\cdot 1=120$

En otras palabras, podemos decir que el factorial de un número $n$, es la multiplicación de $n$ con todos sus antecesores hasta llegar al número 1. Además, podemos ver que el comportamiento anterior es muy similar al comportamiento de la función recursiva que definimos antes: func(). De tal manera, implementaremos una función recursiva para calcular el factorial de un número dado $n$, siguiendo la siguiente idea:

Una vez ingresado el valor de $n$, podemos calcular el factorial de $n$ como sigue: $$ n!=n\cdot (n-1)\cdot (n-2)\cdots 2\cdot 1=n\cdot (n-1)! $$ Luego, si queremos hallar el valor de $(n-1)!$ calculamos: $$ (n-1)!=(n-1)\cdot (n-2)! $$ y así sucesivamente hasta que llegamos a calcular $2!=2$, es decir, continuaremos calculando factoriales hasta que lleguemos a que dicho cálculo ya es un número fijo, o a que nuestro cálculo ya no involucra el símbolo $!$. Luego, dado que $2!=2$, regresamos para calcular los factoriales que quedaron pendientes:

$3!=3\cdot 2!=3\cdot 2=6$ y regresamos al factorial anterior
$4!=4\cdot 3!=4\cdot 6=24$ y regresamos al factorial anterior
$5!=5\cdot 4!=5\cdot 24=120$ y regresamos al factorial anterior $$ \vdots $$
$(n-1)!=(n-1)\cdot (n-2)!$, donde, para este punto, el valor de $(n-2)!$ ya es conocido, de modo que el número $(n-1)!$ también ya lo podemos conocer. Finalmente regresamos al factorial anterior
$n!=n\cdot (n-1)!$, donde, para este punto, el valor de $(n-1)!$ ya es conocido por lo cual habremos acabado pues, con lo anterior, ya podremos conocer el valor de $n!$.

En otras palabras, la función recursiva que buscamos implementar calculará el factorial de un número $n$, intentando calcular primero $(n-1)!,(n-2)!,(n-3)!,(n-4)!,\ldots,4!,3!,2!$. Como aún no puede calcular $(n-1)!$ pasa a intentar calcular $(n-2)!$; como aún no puede calcular $(n-2)!$ pasa a intentar calcular $(n-3)!$, y así sucesivamente hasta que lográ calcular $2!=2$. Una vez que logramos calcular un valor fijo de un factorial, la función regresará a calcular los factoriales que quedaron pendientes. Esto es, ahora la función calculará $3!, 4!,\ldots, (n-3)!, (n-2)!,(n-1)!,n!$, pues, como ya conoce el valor de $2!$, ya puede calcular el valor de $3!$; como ya conoce el valor de $3!$ ya puede calcular el valor de $4!$ y así hasta llegar al valor de $(n-2)!$; como ya conoce el valor de $(n-2)!$ ya puede calcular el valor de $(n-1)!$ y, dado que ya conocemos este valor, finalmente podemos calcular el valor de $n!$.

Estamos preparados ahora para definir una función que calcule el valor de $n!$:

In [4]:

def factorial(n) -> int:
    """Función de un parámetro que retorna un número
    entero. Esta función calcula el factorial de un
    número n dado."""
    # Esta variable almacenara el valor de las multiplicaciones
    # n(n-1)!. Lo inicializamos en uno
    fac_num = 1
    # Nuestra funcion solo actuara cuando el valor de
    # la n sea mayor a cero
    if n > 0:
        # implementamos la multiplicacion n(n-1)!
        # como explicamos antes. Esto es
        # n(n-1)! --> n * factorial(n-1)
        fac_num = n * factorial(n-1)
    else:
    # Cuando la n sea menor a 1 nuestra funcion finaliza
        print("fin")
    # Retornamos el valor final del factorial calculado
    return fac_num

# Probamos nuestra funcion
print(f"El valor de 5! = {factorial(5)}")

fin
El valor de 5! = 120

In [6]:

print(f"El valor de 6! = {factorial(6)}")

fin
El valor de 6! = 720

In [8]:

print(f"El valor de 10! = {factorial(10)}")

fin
El valor de 10! = 3628800

Podemos modificar la definición de nuestra función para observar una salida más visual:

In [27]:

def factorial2(n):
    """Función de un parámetro que retorna un número
    entero. Esta función calcula el factorial de un
    número n dado."""
    # Observamos el numero de ejecucion actual
    print("Número en ejecución", n)
    fac_num = 1
    if n > 1:
        fac_num = n * factorial2(n - 1)
        # Mostramos el valor de fac_num calculado
        print("Resultado", fac_num)
    else:
        print("Fin")
    return fac_num

# probamos nuestra función
print(factorial2(5))

Número en ejecución 5
Número en ejecución 4
Número en ejecución 3
Número en ejecución 2
Número en ejecución 1
Fin
Resultado 2
Resultado 6
Resultado 24
Resultado 120
120

de donde:

Primero se ejecutará en nuestra función el código correspondiente al valor en que n vale 5:

# .
# .
# .
print("Número en ejecución", 5)
    fac_num = 1
    if 5 > 1:
        fac_num = 5 * factorial2(5 - 1)

al ejecutarse la última línea fac_num = 5 * factorial2(4) se manda a llamar de nuevo la misma función factorial2(4) pero ahora con el valor de 4.

Después se ejecutará en nuestra función el código correspondiente al valor en que n vale 4:

# .
# .
# .
print("Número en ejecución", 4)
    fac_num = 1
    if 4 > 1:
        fac_num = 4 * factorial2(4 - 1)

al ejecutarse la última línea fac_num = 4 * factorial2(3) se manda a llamar de nuevo la misma función factorial2(3) pero ahora con el valor de 3. Notemos que hasta ahora tendremos en salida:

Número en ejecución 5
Número en ejecución 4

y así sucesivamente hasta que tenemos

Número en ejecución 5
Número en ejecución 4
Número en ejecución 3
Número en ejecución 2
Número en ejecución 1

Luego, como la condición if n > 1 ya no se cumple cuando n vale 0, entonces se muestra en consola el mensaje Fin, pero para este punto ya sabemos el valor la variable fac_num el cual será de 2, esto es, ya conocemos el valor de $2!$. Así, la ejecución de nuestra función recursiva ahora va en reversa y por ende en la siguiente ejecución se muestra Resultado 6 pues ahora se ha calculado $3!=3\cdot 2!=3\cdot2=6$. Y así sucesivamente hasta que logramos calcular el valor de $n!$:

Resultado 2
Resultado 6
Resultado 24
Resultado 120
120

Curso de introducción a la programación con Python¶

Contenido¶

Introducción ¶

Factorial de un número ¶