Recursión y método del árbol de recursión
Trace las llamadas recursivas en forma de árbol, aplique el teorema maestro y derive las complejidades temporales de merge sort, factorial y variantes de Fibonacci.
Recursión y método del árbol de recursión es una lección gratuita de DSA 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 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.
Recursión y la pila de llamadas
Cuando una función se llama a sí misma, cada llamada añade un marco de pila, que se acumula hasta alcanzar un caso base; después, las llamadas se van desapilando. Visualizar este proceso es el primer paso para analizar la recursión.
def factorial(n):
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive call
# Call chain: factorial(4)
# 4 * factorial(3)
# 3 * factorial(2)
# 2 * factorial(1)
# 1 * factorial(0) -> 1
# Unwinds: 1, 2, 6, 24
print(factorial(5)) # 120El árbol de recursión de Fibonacci
Un árbol de recursión expande cada llamada en sus subllamadas. El Fibonacci ingenuo se divide en dos llamadas cada vez, creando un árbol de aproximadamente 2^n nodos, es decir, O(2^n). Consulte el código.
call_count = [0]
def fib_naive(n):
call_count[0] += 1
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
for n in [5, 10, 15, 20]:
call_count[0] = 0
result = fib_naive(n)
print(f'fib({n})={result}, calls={call_count[0]}')
# Calls roughly double each time n increases by 1Identificar subproblemas repetidos
En ese árbol, las mismas llamadas, como fib(3), se repiten en distintas ramas. Estos subproblemas superpuestos indican que debe utilizar memoización, lo que reduce O(2^n) a O(n).
# Memoised: each unique sub-problem computed once
def fib_memo(n, memo={}):
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
call_count2 = [0]
def fib_counted(n, memo={}):
call_count2[0] += 1
if n in memo: return memo[n]
if n <= 1: return n
memo[n] = fib_counted(n-1, memo) + fib_counted(n-2, memo)
return memo[n]
fib_counted(20)
print(f'calls with memo: {call_count2[0]}') # only 21Árbol de recursión de merge sort
El árbol de merge sort tiene log n niveles, y en cada nivel se realiza un trabajo total de O(n): cada elemento se procesa una vez. Al multiplicarlos se obtiene O(n log n). Consulte el código.
# Merge sort: at each level, n total elements are merged
# Level 0: 1 merge of n elements -> n work
# Level 1: 2 merges of n/2 each -> n work
# Level 2: 4 merges of n/4 each -> n work
# ...log(n) levels...
# Total: n * log(n)
# Verify with operation counter:
def merge_sort_counted(arr):
ops = [0]
def _sort(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r = _sort(a[:m]), _sort(a[m:])
result, i, j = [], 0, 0
while i < len(l) and j < len(r):
ops[0] += 1
if l[i] <= r[j]: result.append(l[i]); i+=1
else: result.append(r[j]); j+=1
return result + l[i:] + r[j:]
return _sort(arr), ops[0]
_, c = merge_sort_counted(list(range(64, 0, -1)))
print(f'Merge ops: {c}') # ~384 ~ 64*log2(64)=384El teorema maestro
El teorema maestro resuelve T(n) = a*T(n/b) + O(n^d) mediante tres casos. Para merge sort (a=2, b=2, d=1), produce O(n log n). Memorice los tres casos para el examen.
# Merge sort: T(n) = 2*T(n/2) + O(n)
# a=2, b=2, d=1, log_b(a)=log2(2)=1=d => O(n log n)
# Binary search: T(n) = 1*T(n/2) + O(1)
# a=1, b=2, d=0, log2(1)=0=d => O(log n)
# Strassen matrix mult: T(n) = 7*T(n/2) + O(n^2)
# a=7, b=2, d=2, log2(7)~2.81 > 2 => O(n^log2(7)) ~ O(n^2.81)
import math
print('log2(7) =', math.log2(7)) # 2.807...Dibujar árboles de recursión paso a paso
Para dibujar un árbol de recursión: coloque T(n) en la parte superior, expanda cada llamada, sume el trabajo de cada nivel y multiplíquelo por el número de niveles. Practique hasta hacerlo de forma automática.
# Factorial: T(n) = T(n-1) + O(1)
# Tree is a chain: n levels, O(1) each -> O(n)
# Fibonacci: T(n) = T(n-1) + T(n-2) + O(1)
# Binary tree of depth n, ~2^n nodes -> O(2^n)
# Merge sort: T(n) = 2*T(n/2) + O(n)
# Log levels, n work each -> O(n log n)
def count_recursive_calls(n, results=[]):
if n <= 1:
results.append(n)
return n
return count_recursive_calls(n-1, results) + count_recursive_calls(n-2, results)
results = []
count_recursive_calls(8, results)
print(f'fib(8) leaf calls: {len(results)}')Recursión exponencial: subconjuntos
Generar todos los subconjuntos es O(2^n): hay exactamente 2^n, por lo que no es posible hacerlo mejor. Cada elemento se incluye o se excluye, construyendo un árbol binario de decisiones. Consulte el código.
def subsets(nums):
result = []
def backtrack(start, current):
result.append(list(current)) # O(n) copy
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return result
nums = [1, 2, 3]
ss = subsets(nums)
print(len(ss)) # 8 = 2^3
print(ss)Recursión de cola y optimización
La recursión de cola ocurre cuando la llamada recursiva es el último paso. Algunos lenguajes reutilizan el marco en ese caso, pero Python no; por eso, las recursiones profundas siguen desbordando la pila. Utilice un bucle en su lugar.
# Tail-recursive factorial (accumulator pattern)
def fact_tail(n, acc=1):
if n == 0:
return acc
return fact_tail(n - 1, n * acc) # tail call
# Python does NOT TCO, so this overflows for large n
# Instead, convert to iterative:
def fact_iter(n):
acc = 1
while n > 0:
acc *= n
n -= 1
return acc
print(fact_tail(10)) # 3628800
print(fact_iter(10)) # 3628800Complejidad espacial de la recursión
Cada llamada recursiva conserva un marco, por lo que la recursión utiliza un espacio O(profundidad). La recursión lineal es O(n); el recorrido DFS de un árbol equilibrado es O(log n). Si profundiza demasiado, se producirá un RecursionError.
import sys
print(sys.getrecursionlimit()) # default 1000
# Increase limit for deep problems
sys.setrecursionlimit(10000)
# Track max depth manually
def max_depth_tracker(n, depth=0, max_seen=[0]):
max_seen[0] = max(max_seen[0], depth)
if n <= 0:
return
max_depth_tracker(n - 1, depth + 1, max_seen)
return max_seen[0]
print(max_depth_tracker(50)) # 50 => O(n) stack framesÁrbol de recursión de quick sort
Quick sort es O(n log n) cuando el pivote es bueno, pero un pivote desfavorable con una entrada ordenada lo degrada a O(n^2). Por eso es importante aleatorizar el pivote. Consulte el código.
import random
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = random.choice(arr) # randomised -> O(n log n) expected
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
return quick_sort(less) + equal + quick_sort(greater)
print(quick_sort([3, 6, 8, 10, 1, 2, 1])) # sortedFunción de potencia: recursión O(log n)
La operación ingenua x^n requiere O(n) multiplicaciones, pero elevar al cuadrado reduce el trabajo a la mitad en cada paso: x^n = (x^(n/2))^2. Así se obtiene un claro O(log n): reducir a la mitad en acción. Consulte el código.
def fast_pow(x, n):
if n == 0: return 1
if n < 0: return 1 / fast_pow(x, -n)
if n % 2 == 0:
half = fast_pow(x, n // 2)
return half * half # O(log n) calls
return x * fast_pow(x, n - 1)
print(fast_pow(2, 10)) # 1024
print(fast_pow(3, 5)) # 243
# Only log2(10)=3-4 recursive calls for n=10Comprobación rápida
Comprobación rápida: demuestre lo que ha aprendido sobre el método del árbol de recursión. Solo es una pregunta; tómese su tiempo. 🌳
Resumen de la lección
Resumen: un árbol de recursión revela el trabajo total, el teorema maestro resuelve las recurrencias de divide y vencerás, y la recursión utiliza un espacio de pila O(profundidad).
Preguntas frecuentes
¿La lección «Recursión y método del árbol de recursión» es gratis?
Sí — el texto completo de «Recursión y método del árbol de recursió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 «Recursión y método del árbol de recursión»?
Trace las llamadas recursivas en forma de árbol, aplique el teorema maestro y derive las complejidades temporales de merge sort, factorial y variantes de Fibonacci. 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 3 de 4.
¿Cuánto tiempo toma la lección «Recursión y método del árbol de recursió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
- Notación Big-O desde cero
- Análisis de bucles y bucles anidados
- Recursión y método del árbol de recursión
- Complejidad espacial y compensaciones