Explorador de árboles de recursión

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=2L-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,2F_1-1=2F_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+(2F_n-1)+(2F_{n-1}-1)=2F_{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{\phi }^{n+1}}{\sqrt{5}}=10^8⟹{\phi }^{n+1}=\frac{10^8\sqrt{5}}{2}=1.1180\times 10^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 \left(1.1180\times 10^8\right)}{\ln \phi }=\frac{18.5323}{0.4812}=38.51$$

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.

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.

   $$\text{fib}:x^2=x+1\Rightarrow \phi =1.6180340;\text{hanoi}:C(n)=1+2C(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.8393^{20}=196,331\text{against}128,287⟹A=0.6534;\text{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$$