Explorador de árboles de recursión

Elige una definición recursiva, fija el valor de n y observa cuántas llamadas realiza, así como cuántas de ellas resuelven un problema que ya se había solucionado antes.

Ejemplo resuelto — Explorador de árboles de recursión

Llamadas realizadas	25
Subproblemas distintos	7
Llamadas por subproblema	3,6
Anidamiento máximo	5
Casos base alcanzados	13
Pasos de combinación	12

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — Explorador de árboles de recursión

Un árbol de recursión tiene un nodo por llamada: la raíz es la llamada que hiciste, y los hijos de un nodo son las llamadas que este realiza. De aquí se extraen tres números. El conteo de nodos representa el tiempo de ejecución en unidades de «una llamada». La altura indica la profundidad que alcanza la pila. Por último, el conteo de nodos diferentes equivale al tiempo de ejecución que obtendrías si cada respuesta se recordara la primera vez que se calcula.

Cómo leer lo que ves

La página se abre en fib(6), cuyo árbol es lo bastante pequeño para dibujarse entero: 25 nodos, 7 de los cuales representan la primera aparición de su subproblema. Por eso la tarjeta de problemas distintos indica 7 y la de llamadas por subproblema muestra 3,6. El anidamiento máximo es 5, a lo largo de fib(6) → fib(5) → … → fib(1). De las 25 llamadas, 13 alcanzan un caso base y las 12 restantes suman dos valores devueltos cada una.

Falla cuando: Las llamadas por subproblema son una promesa sobre la memoización, y Hanói es donde esa promesa se rompe. Hanói en n = 20 reporta 21 subproblemas distintos frente a 2.097.151 llamadas, es decir, 99.864,3 llamadas por subproblema, 95,8 veces la cifra de Fibonacci para el mismo valor de n. Memoizar esto no ahorra nada útil. La respuesta a hanoi(20) es una lista de 1.048.575 movimientos, y devolver una lista recordada cuesta lo mismo que generarla. Una tabla de memoización resulta rentable cuando la respuesta es pequeña y el árbol es inmenso. La respuesta de Fibonacci es un solo entero; la de Hanói es el árbol transcrito por completo.

Fibonacci, calculado contando unos 🖖

Fija n en 20. El árbol contiene 21.891 llamadas. De ellas, 10.946 alcanzan un caso base y las otras 10.945 son sumas. Solo fib(1) devuelve 1, y fib(0) devuelve 0, por lo que 6.765 de esas hojas aportan un uno y 4.181 no aportan nada. F(20) es 6.765, que es exactamente la cantidad de unos. Cada valor que devuelve la recursión es una suma de algunos de ellos, y esto nunca cambia con n. La tarjeta de casos base siempre indicará F(n+1), y los unos presentes en ella siempre sumarán F(n).

Dos árboles de 21.891 llamadas, y solo uno se repite 🖖

La versión ingenua de fib(20) y el ordenamiento por mezcla de 10.946 elementos hacen exactamente el mismo número de llamadas: 21.891, divididas en 10.946 casos base y 10.945 pasos de combinación. Tres de las seis tarjetas arrojan resultados idénticos. Además, ambas definiciones se ramifican en dos en cada nodo interno, de modo que la ramificación no es lo que las diferencia. La tarjeta de subproblemas distintos es la clave: 21 frente a 21.891. Una tabla de memoización reduce el árbol de Fibonacci a 21 unidades de trabajo y deja el del ordenamiento por mezcla en 21.891. Esto ocurre porque las mitades del ordenamiento por mezcla son porciones diferentes de un mismo arreglo, y una respuesta almacenada para «una secuencia de 5.473 elementos» correspondería a los 5.473 elementos equivocados.

Un simple 1 restado separa φⁿ de 2ⁿ 🖖

Hanói y Fibonacci recurren dos veces y alcanzan casi la misma profundidad, 20 frente a 19. Hanói en n = 20 realiza 2.097.151 llamadas. Fibonacci realiza 21.891, lo que supone 95,8 veces menos. La única diferencia en el código es el segundo argumento recursivo. Hanói se llama a sí misma en n−1 dos veces, mientras que Fibonacci lo hace en n−1 y luego en n−2. Esa única resta reduce la base de la función exponencial de 2 a φ = 1,618, y la brecha no deja de aumentar. Para n = 30 la diferencia es de 2.147.483.647 frente a 2.692.537, un factor de 798.

Problemas resueltos al detalle

La forma cerrada del recuento de llamadas cuando fib(10) ingenuo hace 177 llamadas 6 pasos
La herramienta dice que la versión ingenua de fib(10) realiza 177 llamadas y fib(11) realiza 287. Encuentra la forma cerrada para el conteo de llamadas, demuéstrala y luego calcula hasta dónde llega la función ingenua de Fibonacci en un segundo dentro de una máquina capaz de procesar 10⁸ llamadas por segundo.
1. Suma uno a cada conteo: 178 y 288. Ambos son pares y sus mitades son 89 y 144, que corresponden a F₁₁ y F₁₂. Por tanto, la conjetura es C(n) = 2F(n+1) − 1, con F(1) = F(2) = 1.
  
  $C (10) = 177, C (11) = 287 ⟹ \frac{178}{2} = 89 = F_{11}, \frac{288}{2} = 144 = F_{12}$
2. El árbol explica de dónde surge esa duplicación. Cada nodo interno hace exactamente dos llamadas y cada hoja no hace ninguna. De este modo, un árbol con L hojas tiene L − 1 nodos internos y 2L − 1 nodos en total. La herramienta reporta 89 casos base para n = 10, y 2 × 89 − 1 = 177.
  
  $N = 2 L - 1 ⟹ 2 \times 89 - 1 = 177$
3. Primero los casos base. fib(0) y fib(1) devuelven su valor sin recurrir, de modo que C(0) = C(1) = 1, y tanto 2F(1) − 1 como 2F(2) − 1 equivalen a 1.
  
  $C (0) = C (1) = 1, 2 F_{1} - 1 = 2 F_{2} - 1 = 1$
4. Ahora el paso de inducción. Supón que la fórmula se cumple para n − 1 y n − 2. La llamada en n equivale a un nodo más sus dos subárboles. Debajo, los dos números de Fibonacci se colapsan por la propia definición de la secuencia. Establecer n = 11 da como resultado 2 × 144 − 1 = 287, que es justo lo que imprime la herramienta.
  
  $C (n) = 1 + C (n - 1) + C (n - 2) = 1 + (2 F_{n} - 1) + (2 F_{n - 1} - 1) = 2 F_{n + 1} - 1$
5. Deja el árbol a un lado. La fórmula de Binet establece que F(m) = (φ^m − ψ^m)/√5 con φ = 1,6180 y |ψ| < 1, por lo que F(m) es φ^m/√5 redondeado al entero más cercano, y C(n) ≈ 2φⁿ⁺¹/√5. Un segundo a 10⁸ llamadas por segundo permite realizar 10⁸ llamadas, lo cual fija φⁿ⁺¹ en 1,1180 × 10⁸.
  
  $C (n) \approx \frac{2 φ ^{n + 1}}{5} = 1 0^{8} ⟹ φ^{n + 1} = \frac{1 0 ^{8} 5}{2} = 1.1180 \times 1 0^{8}$
6. Toma logaritmos. ln(1,1180 × 10⁸) = 18,5323 y ln φ = 0,4812, así que n + 1 = 38,51 y n = 37,5. Redondea hacia abajo, ya que una llamada fraccionaria no termina.
  
  $n + 1 = \frac{ln ( 1.1180 \times 1 0 ^{8} )}{ln φ} = \frac{18.5323}{0.4812} = 38.51$
Respuesta

n = 37. La herramienta confirma a los dos vecinos: 78.176.337 llamadas en n = 37 y 126.491.971 en n = 38. A partir de ahí, cada aumento de 1,44 en n duplica el trabajo, porque ln 2 / ln φ = 1,44. Mientras tanto, la tarjeta de subproblemas distintos en n = 37 indica 38. Setenta y ocho millones de llamadas para responder treinta y ocho preguntas es el argumento a favor de la programación dinámica en una sola frase.
Tres ramas que crecen más despacio que dos 6 pasos
Las escaleras de tres pasos se llaman a sí mismas tres veces en cada nodo; las Torres de Hanói se llaman dos. Carga Escaleras 20, tres ramas, averigua cuál de los dos árboles crece más deprisa y decide cuánto vale el factor de ramificación como guía.

Abre este problema en la herramienta
1. Lee la recurrencia de la definición y no del dibujo. Una llamada para el propio nodo, luego tres más en n − 1, n − 2 y n − 3, y todo lo que esté en 2 o por debajo devuelve su valor sin recurrir.
  
  $C (n) = 1 + C (n - 1) + C (n - 2) + C (n - 3), C (0) = C (1) = C (2) = 1$
2. Supón que el conteo crece geométricamente, C(n) ≈ A xⁿ, y sustituye. Divide todo entre x elevado a n − 3 y el 1 inicial se queda atrás como ruido de orden inferior, lo que deja una cúbica. Su única raíz real es 1,8392868, la constante tribonacci.
  
  $C (n) \sim A x^{n} ⟹ x^{3} = x^{2} + x + 1 ⟹ x = 1.8392868$
3. La misma receta en las otras dos definiciones. Fibonacci se llama en n − 1 y n − 2, así que x² = x + 1 y la raíz es φ = 1,6180340. Hanói se llama dos veces en n − 1, así que x = 2 y no hay nada que resolver.
  
  $fib : x^{2} = x + 1 \Rightarrow φ = 1.6180340; hanoi : C (n) = 1 + 2 C (n - 1) \Rightarrow x = 2$
4. Compruébalo en lugar de creértelo. Pon n en 29, lee la tarjeta de llamadas realizadas, pon n en 30, léela otra vez y divide. Las escaleras dan 1,83929, Fibonacci 1,61803 y Hanói exactamente 2. Cinco decimales en las tres.
  
  $\frac{C ( 30 )}{C ( 29 )} : \frac{56 , 843 , 233}{30 , 905 , 041} = 1.83929, \frac{2 , 692 , 537}{1 , 664 , 079} = 1.61803, \frac{2 ^{31} - 1}{2 ^{30} - 1} = 2.00000$
5. Lo que la raíz no te da es el conteo. 1,8393²⁰ es 196.331 mientras que la tarjeta marca 128.287, así que hay un factor de 0,65 delante; las llamadas de Hanói son exactamente 2ⁿ⁺¹ − 1, un factor de 2. Los casos base fijan esa constante y la recurrencia fija la raíz, y solo la raíz decide quién gana a la larga.
  
  $1.839286 8^{20} = 196, 331 against 128, 287 ⟹ A = 0.6534; hanoi : C (n) = 2^{n + 1} - 1, A = 2$
6. El largo plazo llega pronto aquí. En n = 20 Hanói hace 16,3 veces más llamadas que las escaleras, y en n = 30 hace 37,8 veces más. La proporción se duplica cada 8,3 pasos, ya que ln 2 dividido entre ln(2 ÷ 1,8393) es 8,27.
  
  $\frac{2 ^{21} - 1}{128 , 287} = 16.3, \frac{2 ^{31} - 1}{56 , 843 , 233} = 37.8, \frac{ln 2}{ln ( 2/1.8393 )} = 8.27$
Respuesta

Hanói crece más deprisa, 2 contra 1,8393, y la tercera rama no le cuesta a las escaleras nada que no puedan pagar. El factor de ramificación es una cota superior de la tasa de crecimiento, y solo se alcanza cuando cada hijo es un paso más pequeño. Las escaleras gastan dos de sus tres llamadas en argumentos que bajan 2 y 3, y esos subárboles son lo bastante baratos como para no llegar nunca a sumar la rama que parecían haber ganado.

Lo que hay que quedarse es la receta, porque funciona con una definición que nadie te ha resuelto antes. Cuenta los hijos, anota cuánto baja el argumento cada uno, escribe x elevado a la bajada mayor como suma de x elevado a las bajadas restantes y toma la mayor raíz real. Va con una advertencia: esto es un hecho sobre el árbol ingenuo, y el árbol ingenuo no es lo que nadie escribiría. La tarjeta de subproblemas distintos marca 21 en n = 20 para las escaleras y 21 para Hanói, así que una memoización elimina el exponente por completo y la tasa de crecimiento deja de importar.

$x^{k} = j \sum m_{j} x^{k - j} (m_{j} children at n - j, k = max j) : 1.8393 < 2$

Ruta de aprendizaje

Contar trabajo, no segundos

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.