Compensaciones entre recursión e iteración
Convierta factorial y Fibonacci recursivos en bucles iterativos y explique cuándo el límite de recursión y el tamaño de la pila de Python hacen preferible la iteración.
Compensaciones entre recursión e iteración es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 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 Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
La dualidad recursiva-iterativa
Todo algoritmo que puede escribirse de forma recursiva también puede escribirse de forma iterativa, y viceversa. La versión recursiva suele reflejar más fielmente la definición matemática del problema, mientras que la versión iterativa ofrece un control explícito de la memoria y evita los riesgos de desbordamiento de la pila. Elegir entre ambas es una decisión pragmática basada en la legibilidad, los límites de profundidad y los requisitos de rendimiento.
En las entrevistas, poder presentar ambas versiones y explicar las ventajas y desventajas de cada una es una señal clara de dominio.
Factorial: recursivo frente a iterativo
El factorial es el ejemplo canónico. La versión recursiva codifica directamente la definición matemática n! = n × (n-1)!. Utiliza un espacio de pila O(n) debido a los n valores de retorno pendientes. La versión iterativa recorre un bucle de 1 a n y utiliza un espacio O(1). Para n = 1000, la versión recursiva alcanza el límite predeterminado de Python; la versión iterativa admite valores de n arbitrariamente grandes.
def factorial_rec(n):
if n == 0:
return 1
return n * factorial_rec(n - 1) # O(n) stack
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i # O(1) stack
return result
print(factorial_rec(10)) # 3628800
print(factorial_iter(10)) # 3628800
# Large n: iterative works, recursive may overflow
print(factorial_iter(1000) > 0) # True (Python handles big ints)Fibonacci: exponencial frente a lineal
El Fibonacci recursivo ingenuo tiene un tiempo de ejecución O(2^n), lo que resulta desastrosamente lento para valores grandes de n. La versión iterativa tiene un tiempo O(n) y un espacio O(1). La recursión con memoización (en la próxima lección) también tiene un tiempo O(n), pero un espacio O(n) debido al diccionario de memoización y a la pila O(n). Para Fibonacci, el enfoque iterativo es óptimo en todos los aspectos. Para n = 50, la recursión ingenua tarda segundos; la iterativa tarda microsegundos.
import time
def fib_rec(n):
if n <= 1: return n
return fib_rec(n-1) + fib_rec(n-2) # O(2^n)
def fib_iter(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a # O(n) time, O(1) space
# Timing comparison for n=35
start = time.time()
fib_rec(35)
print(f'Recursive n=35: {time.time()-start:.3f}s')
start = time.time()
fib_iter(35)
print(f'Iterative n=35: {time.time()-start:.6f}s')
print(fib_iter(100)) # handles large nRecorrido de árboles: recursivo vs iterativo
El recorrido recursivo de árboles resulta naturalmente claro porque la estructura del árbol refleja la recursividad. Sin embargo, en un árbol muy desequilibrado (esencialmente una lista enlazada), la profundidad de la recursión es igual a la altura del árbol = O(n), lo que puede provocar un desbordamiento de pila. La versión iterativa, que utiliza una pila explícita, no tiene un límite de profundidad y permite que el tamaño de la pila crezca en el heap en lugar de hacerlo en la pila de llamadas.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val; self.left = left; self.right = right
def preorder_rec(root, result=None):
if result is None: result = []
if root:
result.append(root.val)
preorder_rec(root.left, result)
preorder_rec(root.right, result)
return result
def preorder_iter(root):
if not root: return []
result, stack = [], [root]
while stack:
node = stack.pop()
result.append(node.val)
if node.right: stack.append(node.right)
if node.left: stack.append(node.left)
return result
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(preorder_rec(root)) # [1, 2, 4, 5, 3]
print(preorder_iter(root)) # [1, 2, 4, 5, 3]Merge sort: recursivo vs iterativo (de abajo arriba)
Merge sort es naturalmente recursivo (dividir, aplicar recursividad, mezclar). El merge sort iterativo de abajo arriba evita por completo la recursividad: comienza con subarreglos de tamaño 1, mezcla pares adyacentes en subarreglos de tamaño 2, después de tamaño 4, etc., duplicando el tamaño del subarreglo en cada pasada. El merge sort de abajo arriba tiene un tiempo de ejecución de O(n log n), un espacio de O(n) (para el búfer de mezcla) y un espacio de pila de O(1).
def merge_sort_iterative(arr):
n = len(arr)
size = 1
while size < n:
for start in range(0, n, 2 * size):
mid = min(start + size, n)
end = min(start + 2 * size, n)
left = arr[start:mid]
right = arr[mid:end]
# Merge
i = j = 0
for k in range(start, end):
if i < len(left) and (j >= len(right) or left[i] <= right[j]):
arr[k] = left[i]; i += 1
else:
arr[k] = right[j]; j += 1
size *= 2
return arr
print(merge_sort_iterative([5, 2, 4, 6, 1, 3])) # [1,2,3,4,5,6]Cuándo la recursividad es claramente mejor
La recursividad resulta especialmente útil cuando el problema tiene una estructura similar a un árbol que se corresponde directamente con el grafo de llamadas, cuando los casos base son naturales y cuando la profundidad está acotada (O(log n) en árboles equilibrados y en divide y vencerás). Algunos ejemplos son el análisis de JSON, el recorrido de directorios, los árboles de juego y los problemas de backtracking. En estos casos, el código recursivo es más corto, claro y fácil de demostrar que la versión iterativa equivalente.
# Recursion is clearest for JSON-like nested structures
def flatten(nested):
result = []
for item in nested:
if isinstance(item, list):
result.extend(flatten(item)) # recurse on sub-list
else:
result.append(item)
return result
print(flatten([1, [2, [3, 4], 5], 6])) # [1, 2, 3, 4, 5, 6]
print(flatten([])) # []
print(flatten([[1, [2]], [3, [4, [5]]]])) # [1, 2, 3, 4, 5]Cuándo la iteración es claramente mejor
La iteración es la opción adecuada cuando: la profundidad es O(n) y n es grande (más de ~500 en código Python seguro), las versiones recursiva e iterativa son igual de legibles (Fibonacci, factorial) o el problema es fundamentalmente secuencial y no tiene una descomposición natural en subproblemas. Los bucles simples que procesan arreglos de izquierda a derecha —sumas acumuladas, ventanas deslizantes y dos punteros— siempre deben implementarse de forma iterativa.
# Iterative is clearest for sequential array processing
def running_max(nums):
result = []
curr_max = float('-inf')
for n in nums:
curr_max = max(curr_max, n)
result.append(curr_max)
return result
print(running_max([3, 1, 4, 1, 5, 9, 2, 6])) # [3,3,4,4,5,9,9,9]
# No natural recursion here — iteration is the only sensible choiceConvertir la recursividad de DFS en iteración
Un enfoque sistemático: cualquier DFS recursivo puede convertirse en iterativo colocando los argumentos de la llamada recursiva en una pila explícita. La idea clave es que la llamada recursiva f(args) equivale a apilar args y ejecutar un bucle. Para el procesamiento en posorden (cuando necesita los resultados de los hijos antes que los del padre), puede necesitar un enfoque de dos pasadas o una marca de visitado.
# Post-order iterative using two stacks
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val=val; self.left=left; self.right=right
def postorder_iter(root):
if not root: return []
s1, s2 = [root], []
while s1:
node = s1.pop()
s2.append(node.val)
if node.left: s1.append(node.left)
if node.right: s1.append(node.right)
return s2[::-1] # reverse gives post-order
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(postorder_iter(root)) # [4, 5, 2, 3, 1]Sobrecarga de rendimiento de la recursividad
Cada llamada recursiva en Python tiene una sobrecarga considerable: se crea un nuevo frame (asignando memoria en el heap), se inicializan las variables locales y se almacena un puntero a la dirección de retorno. Los benchmarks muestran que la sobrecarga de una llamada a función en Python es de aproximadamente 100–200 nanosegundos por llamada. Para una profundidad de recursión de 10^6, esto suma entre 0,1 y 0,2 segundos de sobrecarga pura, independientemente del trabajo del algoritmo. Los bucles iterativos evitan por completo esta sobrecarga.
import time
def rec_sum(n):
if n == 0: return 0
return n + rec_sum(n - 1)
def iter_sum(n):
total = 0
for i in range(n + 1):
total += i
return total
import sys; sys.setrecursionlimit(10000)
n = 5000
start = time.time()
for _ in range(100): rec_sum(n)
print(f'Recursive sum({n}) x100: {(time.time()-start)*1000:.2f}ms')
start = time.time()
for _ in range(100): iter_sum(n)
print(f'Iterative sum({n}) x100: {(time.time()-start)*1000:.2f}ms')Tomar decisiones en una entrevista
En una entrevista de programación, si tiene opción, pregúntese: «¿La profundidad de la recursión está acotada por O(log n)?». Si la respuesta es afirmativa, la recursividad es adecuada. «¿La profundidad de la recursión es O(n)?»; prefiera la iteración o mencione que convertiría la solución en iterativa para producción. «¿El problema tiene una estructura natural de árbol o de divide y vencerás?»; opte preferentemente por la recursividad. «¿El problema consiste en un recorrido secuencial?»; utilice la iteración.
Explique siempre su razonamiento: «Usaré recursividad porque la profundidad es O(log n) en un BST equilibrado, por lo que el espacio de pila O(log n) es aceptable».
Resumen: tabla de ventajas y desventajas
En resumen, el código recursivo suele ser más corto y refleja la estructura del problema, pero consume un espacio de pila O(profundidad) y tiene la sobrecarga de las llamadas a funciones. El código iterativo es más largo, pero utiliza un espacio de pila O(1) y evita los límites de la recursividad. La recursividad memoizada (en la siguiente lección) es un punto intermedio: conserva la claridad de la recursividad y elimina los cálculos repetidos. Analice siempre de forma explícita la complejidad espacial, incluido el espacio de la pila de llamadas.
rows = [
('Factorial', 'O(n) / O(1)', 'O(n) / O(1)', 'Same time; iter wins on space'),
('Fibonacci', 'O(2^n) / O(n)', 'O(n) / O(1)', 'Iter massively wins'),
('Binary search','O(log n) / O(log n)', 'O(log n) / O(1)', 'Iter wins on space'),
('Tree DFS', 'O(n) / O(h)', 'O(n) / O(h)', 'Equal; rec cleaner'),
('Merge sort', 'O(n log n) / O(log n)', 'O(n log n) / O(1)', 'BU-iter wins on stack'),
]
for name, rec, it, note in rows:
print(f'{name:<15} rec={rec:<22} iter={it:<22} {note}')Comprobación rápida
Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Repaso de la lección
En esta lección ha aprendido que: se prefiere la recursividad cuando la profundidad es O(log n) o el problema tiene una estructura natural de árbol; la iteración, cuando la profundidad es O(n) o el problema es secuencial; el Fibonacci recursivo ingenuo tiene un coste de O(2^n), mientras que la versión iterativa tiene un tiempo de ejecución de O(n) y un espacio de O(1); y cualquier DFS recursivo puede convertirse en iterativo gestionando una pila explícita en el heap. A continuación aplicaremos memoización para eliminar las llamadas recursivas redundantes.
Preguntas frecuentes
¿La lección «Compensaciones entre recursión e iteración» es gratis?
Sí — el texto completo de «Compensaciones entre recursión e iteració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 Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Compensaciones entre recursión e iteración»?
Convierta factorial y Fibonacci recursivos en bucles iterativos y explique cuándo el límite de recursión y el tamaño de la pila de Python hacen preferible la iteración. Practicas Coding 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 Coding Interview Prep?
No se requiere experiencia previa. Coding 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 3 de 4.
¿Cuánto tiempo toma la lección «Compensaciones entre recursión e iteració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 Coding Interview Prep?
Sí. Cada lección de Coding 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