Recursión

Cuando escribimos programas, usualmente llamamos distintas funciones para realizar una tarea muy específica. Por ejemplo, utilizamos sqrt para calcular la raíz cuadrada de un número, o llamamos a las funciones max o min para hallar el valor máximo o mínimo de un conjunto de números. La recursión es el proceso de llamar a la misma función desde sí misma. Así, si hemos implementado una función con el nombre f y en algún lugar del cuerpo de f volvemos a llamar a la función f (normalmente con argumentos distintos), estaríamos haciendo una llamada recursiva:

def f(n):                                   # Define una función llamada f
    print(f'f() called with argument {n}')  # Imprime en cada llamada (para demostración)
    if n <= 0:                              # Se detiene si n es negativo
        print('Let\'s stop here...')
    else:                                   # De lo contrario, llama a f con un número menor
        f(n - 1)

f(10)

Esto es lo que imprimiría el programa

f() called with argument 10
f() called with argument 9
f() called with argument 8
f() called with argument 7
f() called with argument 6
f() called with argument 5
f() called with argument 4
f() called with argument 3
f() called with argument 2
f() called with argument 1
f() called with argument 0
Let's stop here...

Este es un ejemplo sencillo que muestra cómo podría implementarse una función recursiva muy básica. En casos más reales, normalmente se realizan computaciones dentro de la función y se devuelven valores tras dichos cálculos, en lugar de limitarse a imprimir mensajes.

En problemas algorítmicos, la recursión puede ser muy útil, en especial cuando se trabaja con grafos, algoritmos de ordenamiento avanzados o backtracking (que veremos más adelante en el curso). Los problemas que requieren recursión son muy comunes, y a veces es mucho más fácil implementar una solución recursiva que una solución iterativa con bucles.

Video preview — Un video de Reducible - 5 Simple Steps for Solving Any Recursive Problem

El proceso de resolver un problema grande dividiéndolo recursivamente en problemas más pequeños, hasta llegar al caso más simple o fácil de manejar, se entiende mejor con el concepto llamado “leap of faith (salto de fe) recursivo”.

Recursive Leap of Faith

Al implementar una solución recursiva, normalmente se crea una función que en algún punto se llama a sí misma. A esta parte se le conoce como la llamada recursiva.

Lo bueno de las soluciones recursivas es que podemos asumir que la función funciona correctamente cuando se llama con argumentos simples, y luego implementamos el comportamiento correcto para los casos más complejos. De forma similar a como empleamos otras funciones (sqrt, max, abs, etc.), podemos suponer que la función funciona para argumentos más pequeños o simples, y usar esos resultados para construir el resultado actual.

💡

La única condición es asegurarnos de que la función llegue a su caso base (el caso más simple). De lo contrario, la función recursiva se ejecutaría infinitamente y podría ocasionar un StackOverflow.

Como demostración de cómo se podría realizar un cálculo dentro de una función recursiva, probemos a calcular la suma de todos los números desde 0, 1, 2, …, n dado un número n.

Implementemos la función sum paso a paso. El primer paso es asegurarnos de que la función funcione correctamente en el caso más sencillo (calcular de forma adecuada la suma para n siendo 0 o 1):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:         # En caso de que n sea 0 => la suma es 0
        return 0       # Se detiene la ejecución aquí
    if n == 1:         # En caso de que n sea 1 => la suma es 1
        return 1       # Se detiene la ejecución aquí

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> None (porque aún no hemos implementado esa parte)

Teniendo esta parte de la función, podemos usar el hecho de que sum(0) devolverá siempre 0 de forma correcta, mientras que sum(1) devolverá siempre 1. La función funcionará sin problemas incluso si llamamos a sum con argumentos 0 o 1 desde dentro de la propia función sum.

Así pues, podemos avanzar un paso más e implementar la función sum para n = 2 y n = 3, aprovechando que ya contamos con los resultados de sum(1) y sum(0):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:             # Si n es 2, sumamos 2 al resultado de sum(1)
        return n + sum(1)  # o n + sum(n - 1)
    if n == 3:             # Si n es 3, sumamos 3 al resultado de sum(2)
        return n + sum(2)  # o n + sum(n - 1)

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> None (todavía no implementado)

De esta forma, vemos claramente que la función sum funciona de manera correcta para valores pequeños como 0, 1, 2 y 3.

Teniendo esto, podemos implementar la función para otros valores mayores de n. El único requisito es llegar a esos valores más pequeños (0, 1, 2 o 3) cuando se llame a la función sum desde ella misma. Así, para valores de n como 4, 5 o 6, etc., podemos usar el hecho de que para calcular sum(4), basta con sumar 4 al resultado de sum(3), mientras que para calcular sum(5), sumamos 5 al resultado de sum(4):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return n + sum(1)
    if n == 3:
        return n + sum(2)
    # Para todos los demás casos (4, 5, 6, ...)
    return n + sum(n - 1)  

print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...

Los elementos clave de una función recursiva son:

Caso base: Una condición que detiene la recursión. Sin esto, la función se llamaría a sí misma indefinidamente, provocando un bucle infinito. En este ejemplo, corresponde a n == 0 y n == 1.

Paso recursivo: El lugar donde la función se llama a sí misma, normalmente con un argumento distinto. En este ejemplo, se ve en sum(n - 1).

Dado que las llamadas para n == 1, n == 2 y n == 3 son exactamente iguales que las de n == 4, n == 5, etc., incluso podemos simplificar la función sum dejando solo un caso base (cuando n == 0):

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    return n + sum(n - 1)  

print(sum(2))          # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...

Así, usando el “leap of faith (salto de fe) recursivo”, asumimos/sabemos que la función funciona correctamente para casos más pequeños o simples y, a partir de eso, construimos el resto de la función basándonos en esos casos sencillos. Esto ayuda a entender cómo funcionan las funciones recursivas y cómo implementarlas.

💡

Llamar recursivamente a la función es como llamar a una función completamente distinta que, con toda seguridad, sabes que funcionará con los argumentos proporcionados.

Reto

Implementa una función recursiva que calcule n! módulo .

Entrada

La entrada contiene un solo número entero n (1 ≤ n ≤ 1000).

Salida

El programa debe imprimir el resultado de n! módulo .

Ejemplos

Entrada	Salida
5	120
10	3628800

Recursive Leap of Faith

Reto

Entrada

Salida

Ejemplos

Constraints

To check your solution you need to sign in

Sign in to continue