Recursión en Python

Problema

¿Cuántas formas de ordenarlos hay?

En la estantería hay 5 libros. ¿De cuántas formas puedes ordenarlos? Para el primer lugar hay 5 opciones, para el segundo 4, después 3, 2 y 1: 5 · 4 · 3 · 2 · 1 = 120. Esto es un factorial, y se escribe 5!.

Con un bucle ya sabes hacerlo:

def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result


print(factorial_loop(5))

Míralo también así: 5! = 5 · 4!. Y 4! = 4 · 3!. La tarea se resuelve mediante la misma tarea, solo que más pequeña. ¿Puede la función decir justo eso?

La idea

Una función que se llama a sí misma

Puede. Una función que se llama a sí misma se llama recursiva, y el enfoque es la recursión.

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)


print(factorial(5))

Dos cosas hacen que funcione:

Un caso base. Un caso que se resuelve directamente, sin una llamada nueva. Aquí: 1! = 1.
Una tarea más pequeña. Cada llamada se llama a sí misma con un número más cerca del caso base: n - 1.

Míralo

La pila de llamadas

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)


print(factorial(3))  # 6

Paso a paso, en palabras

El programa llama a factorial(3).
Memoria nueva para factorial con n = 3.
3 no es 1, así que la función llama a factorial(2) y espera la respuesta.
Lo mismo otra vez: factorial(2) llama a factorial(1). Cada llamada tiene su propio n.
n es 1: este es el caso base. Devuelve 1 sin volver a llamar.
La respuesta baja: 2 * 1 = 2.
Y otra vez: 3 * 2 = 6.
factorial(3) devuelve 6 y el programa lo imprime.

Cada llamada recibe su propia memoria con su propio n. Se apilan una encima de otra y esperan. Esta pila se llama pila de llamadas (call stack). Cuando el caso base devuelve 1, las respuestas bajan una a una y la pila se deshace.

Pruébalo

Bajar y volver a subir

¿Qué imprimirá el programa?

def steps(n):
    if n == 0:
        return
    print(f"bajo {n}")
    steps(n - 1)
    print(f"subo {n}")


steps(2)

Respuesta

bajo 2
bajo 1
subo 1
subo 2

bajo 2
bajo 1
subo 2
subo 1

bajo 2
subo 2
bajo 1
subo 1

Pruébalo

Encuentra el error

sum_to(4) debería devolver 1 + 2 + 3 + 4 = 10. En cambio, el programa se detiene con RecursionError: maximum recursion depth exceeded. ¿En qué línea está el error?

Elige la línea con el error.

La idea

¿Recursión o bucle?

El factorial se puede escribir con un bucle o con recursión. Aquí el bucle es la mejor opción: no acumula memoria por cada llamada. Y Python pone un límite a la pila: con unas 1000 llamadas anidadas detiene el programa con un RecursionError. Ya factorial(1100) no pasa, mientras que el bucle también lo calcula.

La recursión es natural donde algo contiene cosas más pequeñas del mismo tipo: una carpeta con carpetas dentro, una categoría con subcategorías, una rama con ramas. Te encontrarás con tareas así más adelante en el curso. Ahí un bucle se vuelve torpe, mientras que la función recursiva sigue siendo corta.

Más precisamente, para curiosos

El factorial se escribe a menudo con el caso base 0! = 1 (if n == 0:). Así también funciona para 0.

Los enteros en Python no tienen límite: el resultado tiene tantas cifras como haga falta. 30! sale exacto:

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)


print(factorial(30))

265252859812191058636308480000000

El límite de la pila se puede subir con sys.setrecursionlimit(), pero rara vez es buena idea: para cálculos profundos, escribe un bucle.

Pruébalo

Ordena las líneas

La función tiene que calcular una potencia: power(2, 10) es 1024. Ordena sus líneas.

def power(base, exp):
return 1
return base * power(base, exp - 1)
if exp == 0:

Ejercicio

Tareas recursivas

1. Factorial de dos formas. Escribe factorial_loop(n) con un bucle for y factorial(n) con recursión. Lee un número e imprime el resultado de las dos funciones.

El factorial de 5 es 120
El factorial de 5 es 120

2. Suma de cifras. sum_digits(n): la última cifra (n % 10) más la suma de las cifras del resto (n // 10). El caso base es un número de una sola cifra.

3. Fibonacci. Cada número es la suma de los dos anteriores: 0, 1, 1, 2, 3, 5, 8… fib(n) devuelve el número n-ésimo. Pruébalo con 10, y después con 35. ¿Por qué es tan lento? Pista: ¿cuántas veces se calcula cada número?

4. Palíndromo. is_palindrome(s): la primera y la última letra son iguales, y el centro es un palíndromo. El caso base es una palabra de 0 o 1 letras.

sum_digits(2024)
fib(10)
is_palindrome("reconocer")
is_palindrome("ABCDE")

8
55
True
False

Test

Ponte a prueba

1. ¿Qué es la recursión?Dos funciones con el mismo nombreUn bucle dentro de una funciónUna función que se llama a sí misma

2. ¿Por qué una función recursiva necesita un caso base?Para que deje de llamarse a sí mismaPara que vaya más rápidoPara que pueda devolver un resultado

3. factorial(3) llama a factorial(2), y esta llama a factorial(1). ¿Cuántas variables n hay en memoria justo antes de que factorial(1) devuelva su resultado?NingunaTresUna

4. ¿Qué pasa si nunca se llega al caso base?La pila se desborda y el programa se detiene con RecursionErrorEl programa se ejecuta sin fin, sin ningún errorLa función devuelve 0

Recursión

Cookies