Funciones recursivas en Python

En este tutorial vamos a ver la recursividad con ejemplos en Python. La recursividad en programación es una técnica muy potente, ésta se realiza con funciones que se llaman a sí mismas, veámolos cómo una especie de bucle, ya que el mismo código se repetirá varias veces, hasta llegar a la solución.

 

 

 

Vamos a ponernos con los ejemplos, que serán sencillos y cortos para que se puedan asimilar bien.

 

Ejemplo 1 – Factorial

En este ejemplo vamos a resolver el factorial de un número, si quieres saber de qué se trata el factorial visita este enlace. A continuación te dejo el código, y más abajo te explico la función recursiva.

def factorial(numero):
    if(numero == 0 or numero == 1):
        return 1
    else:
        return numero * factorial(numero-1)


if __name__ == "__main__":
    try:
        num = int(input("De que número quieres saber el factorial? "))
        if(num < 0):
            print("El número debe ser mayor o igual a 0")
        else:
            print("El factorial de",num,"es",factorial(num))

    except:
        print("Se espera un número")

Nuestra función recursiva tiene el caso base en el if y el recursivo en el else. Puedes apreciar que el caso base devuelve un 1 y que éste se alcanza cuando el parámetro pasado a la función es 0 ó 1, cuando se alcanza este caso la función no vuelve a realizar llamadas. En el caso recursivo tenemos una llamada de la función a sí misma, pero cómo puedes ver reduciendo el parámetro en 1 (nos acercamos al caso base). La última parte del código ya fuera de la función solo se encarga de pedir un número al usuario y comprobar que es mayor o igual a 0 para llamar a la función, ya que el factorial con números negativos no funciona.

 

Si hacemos la llamada a la función con el número 4, es decir factorial(4), tenemos las siguientes llamadas:

Llamada 1: factorial(4)
Llamada 2: 4*factorial(3)
Llamada 3: 3*factorial(2)
Llamada 4: 2*factorial(1)

Al llamar a factorial con 1, ya no hay más llamadas y devolverá 1, entonces está función retorna devolviendo los resultados a la función que le llamo, el retorno sería así:

factorial(1) = 1
factorial(2) = 2*1
factorial(3) = 3*2
factorial(4) = 4*6

Y ya tenemos nuestro resultado que es 24, de multiplicar los números: 1*2*3*4. A continuación dejo una captura al pedir el factorial de 5, que no es más que multiplicar 5 por el factorial de 4 (que ya sabemos que es 24) dando como resultado 120. También puedes ver que si el usuario inserta mal el número se trata:

 

 

 

Ejemplo 2 – Suma/Resta

En este ejemplo pongo una función recursiva para hacer una suma o resta, desde luego este ejemplo no se suele dar en la vida real, pero como ejemplo nos sirve:

def operar(numero1, numero2):
    if(numero2 == 0):
        return numero1
    elif(numero2 < 0):
        return operar(numero1-1, numero2+1)
    else:
        return operar(numero1+1, numero2-1)


if __name__ == "__main__":
    print("Sumando 10 y 3:", operar(10, 3))
    print("Sumando 5 y -2:", operar(5, -2))

Aquí contamos con un caso base y 2 casos recursivos, esto es así para saber qué camino tocar, ya que dependiendo de que si el número es positivo o negativo tendremos que actuar de manera distinta. La función operar recibe 2 números, y el algoritmo se encargará de ir restando o sumando uno al numero2 y pasándoselo al numero1 (Si numero2 es positivo, le resto 1 a numero2 y se lo sumo a numero1), así hasta que la variable numero2 sea igual a 0.

 

Por ejemplo vamos a sumar 3 + 2 viendo las llamadas.

Llamada 1: operar(3,2)
Llamada 2: operar(4,1)
Llamada 3: operar(5,0)

En este caso al llegar a operar(5,0) no hay nada más que hacer, tenemos el resultado directamente (a diferencia de en el caso del factorial que había hacer la multiplicación). A continuación te dejo el resultado de ejecutar el código: