Marco de recursión: caso base, confianza y construcción
Aplique el método de tres pasos para escribir soluciones recursivas correctas para factorial, potencia y suma de dígitos sin seguir cada llamada.
Marco de recursión: caso base, confianza y construcción es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 1 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
Por qué la recursión resulta difícil
La mayoría de los principiantes intenta seguir mentalmente cada llamada recursiva, lo que rápidamente resulta abrumador incluso con una recursión de cinco niveles de profundidad. El enfoque profesional consiste en utilizar un marco de tres pasos —caso base, confianza y construcción— que le permite escribir funciones recursivas correctas sin simular mentalmente todo el árbol de llamadas.
Este marco a veces se denomina salto de fe: confía en que su función funciona con entradas más pequeñas y utiliza esa suposición para construir la solución para entradas más grandes.
Paso 1: Defina el caso base
El caso base es la entrada más sencilla cuya respuesta se conoce sin recurrir más. Toda función recursiva debe tener al menos un caso base; sin él, la función recurre indefinidamente (desbordamiento de la pila). Algunos buenos casos base son: una lista vacía, un solo elemento, n == 0, n == 1 o un problema que se reduce a una identidad trivial.
Escriba primero el caso base, antes de cualquier lógica recursiva. Identifíquelo preguntándose: '¿Cuál es la versión más pequeña de este problema que puedo responder inmediatamente?'
# Base cases for common problems
def factorial(n):
if n == 0: # base case: 0! = 1
return 1
# ... recursive step below
def sum_list(lst):
if not lst: # base case: sum of empty list is 0
return 0
# ...
def height(node):
if node is None: # base case: height of null node is 0
return 0
# ...
print('Base cases identified')Paso 2: Confíe en la llamada recursiva
La etapa de confianza es ese salto de fe: suponga que su función ya funciona correctamente para cualquier entrada estrictamente menor que la actual. No necesita demostrarlo ahora para cada entrada más pequeña; la demostración inductiva lo garantiza. Simplemente llame a su función con el subproblema más pequeño y confíe en que devuelve el resultado correcto.
Este es el paso que los principiantes suelen omitir, intentando simularlo mentalmente. Resista esa tentación; el método funciona incluso con una recursión de profundidad arbitraria una vez que interiorice el marco.
# Trust example: sum_list([3, 1, 4, 1, 5])
# Trust: sum_list([1, 4, 1, 5]) = 11 (we TRUST this, don't trace it)
# Build: 3 + 11 = 14
# So:
def sum_list(lst):
if not lst:
return 0
# Trust that sum_list(lst[1:]) returns sum of the rest
return lst[0] + sum_list(lst[1:])
print(sum_list([3, 1, 4, 1, 5])) # 14Paso 3: Construya la solución
La etapa de construcción combina el resultado del subproblema en el que se confía con la contribución del elemento actual para producir la respuesta correspondiente a toda la entrada. Por lo general, consiste en una sola línea: aplicar una operación al elemento actual y al resultado de la llamada recursiva. Construcciones habituales: añadir al total, anteponer a una lista, incrementar un contador o combinar dos resultados parciales.
def factorial(n):
if n == 0:
return 1
# Trust: factorial(n-1) gives (n-1)!
# Build: n * (n-1)! = n!
return n * factorial(n - 1)
def power(base, exp):
if exp == 0:
return 1
# Trust: power(base, exp-1) gives base^(exp-1)
# Build: base * base^(exp-1) = base^exp
return base * power(base, exp - 1)
print(factorial(6)) # 720
print(power(2, 10)) # 1024Aplicación del marco a la suma de dígitos
Problema: calcular la suma de los dígitos de un entero no negativo. Caso base: n == 0 → la suma es 0 (o n < 10 → el propio n). Confianza: sumDigits(n // 10) devuelve la suma de todos los dígitos excepto el último. Construcción: añadir el último dígito n % 10 al resultado en el que se confía. El marco produce la solución en tres pasos declarativos.
def sumDigits(n):
if n < 10:
return n # base case: single digit
# Trust: sumDigits(n // 10) gives sum of all digits except last
# Build: add the last digit
return n % 10 + sumDigits(n // 10)
print(sumDigits(0)) # 0
print(sumDigits(7)) # 7
print(sumDigits(123)) # 6
print(sumDigits(9999)) # 36Fibonacci: dos subproblemas
Fibonacci requiere dos llamadas recursivas: fib(n-1) y fib(n-2). Aplique el marco: los casos base son fib(0) = 0 y fib(1) = 1. Confianza: ambas llamadas a problemas más pequeños devuelven los valores correctos de Fibonacci. Construcción: devolver su suma. Esta implementación ingenua tiene una complejidad O(2^n); la corregiremos en la lección sobre memoización.
def fib(n):
if n <= 1:
return n # base cases: fib(0)=0, fib(1)=1
# Trust both smaller sub-problems
return fib(n - 1) + fib(n - 2)
for i in range(8):
print(f'fib({i}) = {fib(i)}') # 0,1,1,2,3,5,8,13Invierta una cadena de forma recursiva
Problema: invertir una cadena de forma recursiva. Caso base: una cadena vacía o de un solo carácter ya está invertida. Confianza: reverse(s[1:]) devuelve la inversión de todo lo que sigue al primer carácter. Construcción: añadir el primer carácter al final del sufijo invertido. El marco ofrece una solución de tres líneas.
def reverse_str(s):
if len(s) <= 1:
return s # base case
# Trust: reverse_str(s[1:]) = reverse of 'ello' for 'hello'
# Build: append first character at end
return reverse_str(s[1:]) + s[0]
print(reverse_str('')) # ''
print(reverse_str('a')) # 'a'
print(reverse_str('hello')) # 'olleh'
print(reverse_str('racecar')) # 'racecar'Conteo recursivo de ocurrencias
Problema: contar recursivamente las ocurrencias de un valor objetivo en una lista. Caso base: una lista vacía; el conteo es 0. Confianza: count(lst[1:], target) devuelve el conteo correspondiente a la cola. Construcción: añadir 1 si el primer elemento coincide con el objetivo; de lo contrario, añadir 0. Cada paso recursivo avanza hacia el caso base al reducir el tamaño de la lista en 1.
def count_occurrences(lst, target):
if not lst:
return 0
# Trust: count in rest of list is handled recursively
# Build: add 1 if first element matches, else 0
return (1 if lst[0] == target else 0) + count_occurrences(lst[1:], target)
print(count_occurrences([1, 2, 3, 2, 4, 2], 2)) # 3
print(count_occurrences([], 5)) # 0
print(count_occurrences([7, 7, 7], 7)) # 3Compruebe si una lista está ordenada
Problema: comprobar recursivamente si una lista está ordenada de forma ascendente. Caso base: una lista de 0 o 1 elementos siempre está ordenada. Confianza: is_sorted(lst[1:]) indica si la cola está ordenada. Construcción: la lista está ordenada si el primer elemento es <= el segundo Y la cola está ordenada. Este es un ejemplo claro en el que la etapa de construcción utiliza una operación AND lógica entre dos condiciones.
def is_sorted(lst):
if len(lst) <= 1:
return True
# Trust: is_sorted(lst[1:]) tells us if tail is sorted
# Build: head <= second element AND tail is sorted
return lst[0] <= lst[1] and is_sorted(lst[1:])
print(is_sorted([])) # True
print(is_sorted([1])) # True
print(is_sorted([1, 2, 3, 4])) # True
print(is_sorted([1, 3, 2, 4])) # FalseBúsqueda binaria recursiva (revisión)
La búsqueda binaria expresada recursivamente mediante el marco: caso base: lo > hi → no encontrado (devuelve -1). Confianza: la llamada recursiva sobre la mitad correcta encuentra el objetivo o devuelve -1. Construcción: calcular mid, comparar y llamar a la mitad correspondiente. La forma recursiva muestra claramente la estructura de divide y vencerás, aunque en producción se prefiere la forma iterativa por utilizar espacio O(1).
def binary_search(arr, target, lo, hi):
if lo > hi: # base case: search space exhausted
return -1
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
# Trust both halves return correct results
if arr[mid] < target:
return binary_search(arr, target, mid + 1, hi)
else:
return binary_search(arr, target, lo, mid - 1)
arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7, 0, len(arr) - 1)) # 3
print(binary_search(arr, 4, 0, len(arr) - 1)) # -1Cuándo usar recursión frente a iteración
La recursión es especialmente adecuada cuando el problema se descompone de forma natural en subproblemas del mismo tipo (árboles, divide y vencerás, retroceso). Se prefiere la iteración cuando: la profundidad de la recursión es grande (con riesgo de desbordamiento de la pila en Python, cuyo valor predeterminado es de aproximadamente 1000), las versiones recursiva e iterativa son igual de claras o el problema es un bucle sencillo (factorial, Fibonacci sin memoización).
Una buena regla general: si dibujar un árbol de recursión le resulta natural, use recursión. Si el árbol es una línea recta (recursión de cola), conviértalo en iteración.
import sys
# Python's default recursion limit
print('Recursion limit:', sys.getrecursionlimit()) # 1000
# A list of 2000 elements would overflow the recursive sum_list
# Use iteration for safety:
def sum_list_iter(lst):
total = 0
for x in lst:
total += x
return total
big = list(range(2000))
print(sum_list_iter(big)) # 1999000 — no stack overflowComprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección aprendió: el marco de tres pasos consiste en Caso base (la respuesta conocida más sencilla), Confianza (suponer que el subproblema está resuelto) y Construcción (combinar el elemento actual con el resultado en el que se confía), escribir primero los casos base y evitar seguir mentalmente árboles de llamadas completos, y usar la iteración cuando la profundidad de la recursión pueda provocar un desbordamiento de la pila o cuando las formas recursiva e iterativa sean igual de claras. A continuación, visualizaremos la pila de llamadas en detalle.
Preguntas frecuentes
¿La lección «Marco de recursión: caso base, confianza y construcción» es gratis?
Sí — el texto completo de «Marco de recursión: caso base, confianza y construcción» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Marco de recursión: caso base, confianza y construcción»?
Aplique el método de tres pasos para escribir soluciones recursivas correctas para factorial, potencia y suma de dígitos sin seguir cada llamada. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 1 de 4.
¿Cuánto tiempo toma la lección «Marco de recursión: caso base, confianza y construcción»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Marco de recursión: caso base, confianza y construcción
- Visualización de la pila de llamadas
- Compensaciones entre recursión e iteración
- Memoización: almacenamiento en caché de resultados recursivos