Búsqueda binaria recursiva
`ordenada` viene de menor a mayor. Devolvé el índice de `x` con búsqueda binaria recursiva, o -1 si no está. Ejemplo: busqueda_binaria_rec([1, 3, 5, 7, 9], 7) → 3
Entrá y llevá tu progreso —ejercicios, medallas y Pokémon— a cualquier dispositivo. 🔄
Si tu cuenta ya tiene progreso guardado, se carga ese al entrar.
Entraste como . Tu progreso se sincroniza solo. 🔄
`ordenada` viene de menor a mayor. Devolvé el índice de `x` con búsqueda binaria recursiva, o -1 si no está. Ejemplo: busqueda_binaria_rec([1, 3, 5, 7, 9], 7) → 3
🎯 Meta: resolver problemas que se repiten en versión más chica con funciones que se llaman a sí mismas.
Una función recursiva se llama a sí misma con un problema más pequeño, hasta llegar a un caso base que la frena. Sin caso base, se llama para siempre y revienta (RecursionError).
Toda recursión tiene:
def factorial(n):
if n == 0: # caso base: 0! = 1
return 1
return n * factorial(n - 1) # caso recursivo
print(factorial(5)) # 5 * 4 * 3 * 2 * 1 = 120
El truco es confiar: asumí que la función ya funciona para el caso más chico, y armá el grande con eso.
def suma_lista(nums):
if not nums: # base: lista vacía suma 0
return 0
return nums[0] + suma_lista(nums[1:]) # primero + suma del resto
Fibonacci es el ejemplo clásico (cada número es la suma de los dos anteriores):
def fib(n):
if n < 2: # base: fib(0)=0, fib(1)=1
return n
return fib(n - 1) + fib(n - 2)
⚠️ Toda recursión se puede escribir con bucles, y viceversa. La recursión brilla cuando el problema es recursivo: árboles, fractales, dividir y conquistar.
P: Una función recursiva SIN caso base…
+ se llama para siempre y revienta (RecursionError)
- devuelve 0
- es más rápida
> El caso base es lo que la frena.
P: `factorial(0)` debe devolver…
+ 1
- 0
- error
> Es el caso base: 0! = 1.
🔁 El Líder Larry te espera: lo simple, recursivo.