Explorador da Árvore de Recursão

A ferramenta assegura que o fib(10) ingênuo opera 177 chamadas e o fib(11) efetua 287. Deduza a forma fechada para a contagem das chamadas, prove a sua precisão, e calcule em seguida a que distância chega o Fibonacci ingênuo num segundo, recorrendo a uma máquina com capacidade para processar 10⁸ chamadas por segundo.

1. Acrescente uma unidade a cada contagem: 178 e 288. Ambas as contagens se revelam pares, com as respetivas metades assentes em 89 e 144, valores que correspondem ao F₁₁ e F₁₂. A conjectura assume então o formato C(n) = 2F(n+1) − 1, estipulando que F(1) = F(2) = 1.

   $$C(10)=177,C(11)=287⟹\frac{178}{2}=89=F_{11},\frac{288}{2}=144=F_{12}$$

2. A árvore clarifica de imediato a origem da referida duplicação. Qualquer nó interno faz rigorosamente duas chamadas e cada folha não faz nenhuma. Como consequência, uma árvore com L folhas contém L − 1 nós internos, somando um total absoluto de 2L − 1 nós. A ferramenta reporta 89 casos-base ao redor de n = 10, e 2 × 89 − 1 = 177.

   $$N=2L-1⟹2\times 89-1=177$$

3. Tratamos os casos-base primeiro. As funções fib(0) e fib(1) retornam desprovidas de ciclos recursivos, fixando C(0) = C(1) = 1. Em simultâneo, tanto 2F(1) − 1 como 2F(2) − 1 resultam inevitavelmente em 1.

   $$C(0)=C(1)=1,2F_1-1=2F_2-1=1$$

4. Avançamos ao passo de indução. Tome como certa a validade da fórmula em n − 1 e n − 2. A chamada no índice n traduz-se na adição de um nó às suas duas subárvores. Os dois números de Fibonacci adjacentes contraem-se devido à própria definição elementar da sequência. Fixando n em 11 obtemos a prova 2 × 144 − 1 = 287, refletindo a cifra que o sistema imprime.

   $$C(n)=1+C(n-1)+C(n-2)=1+(2F_n-1)+(2F_{n-1}-1)=2F_{n+1}-1$$

5. Deixamos as árvores por aqui. A fórmula de Binet impõe a igualdade F(m) = (φ^m − ψ^m)/√5 com φ = 1,6180 e |ψ| < 1, comprimindo F(m) no arredondamento mais próximo de φ^m/√5. Consequentemente, C(n) ≈ 2φⁿ⁺¹/√5. Um segundo com um desempenho de 10⁸ chamadas por segundo rende 10⁸ chamadas, o que fixa de forma peremptória φⁿ⁺¹ nos 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. Aplique os logaritmos. Sabendo de antemão que ln(1,1180 × 10⁸) = 18,5323 e que ln φ = 0,4812, conclui-se que n + 1 = 38,51 e por fim n = 37,5. O arredondamento tem obrigatoriamente de ser feito para baixo, uma vez que uma chamada fracionária jamais atinge o fim do processamento.

   $$n+1=\frac{\ln \left(1.1180\times 10^8\right)}{\ln \phi }=\frac{18.5323}{0.4812}=38.51$$

As escadas de três passos chamam-se a si próprias três vezes em cada nó; as Torres de Hanói chamam-se duas. Carregue Escadas em 20, 3 ramos, descubra qual das duas árvores cresce mais depressa e decida quanto vale o fator de ramificação como guia.

1. Leia a recorrência a partir da definição e não da imagem. Uma chamada para o próprio nó, depois mais três em n − 1, n − 2 e n − 3, e tudo o que esteja em 2 ou abaixo devolve o valor sem recorrer.

   $$C(n)=1+C(n-1)+C(n-2)+C(n-3),C(0)=C(1)=C(2)=1$$

2. Assuma que a contagem cresce geometricamente, C(n) ≈ A xⁿ, e substitua. Divida tudo por x elevado a n − 3 e o 1 inicial fica para trás como ruído de ordem inferior, restando uma cúbica. A sua única raiz real é 1,8392868, a constante tribonacci.

   $$C(n)\sim A{x}^n⟹x^3=x^2+x+1⟹x=1.8392868$$

3. A mesma receita nas outras duas definições. Fibonacci chama-se em n − 1 e n − 2, logo x² = x + 1 e a raiz é φ = 1,6180340. Hanói chama-se duas vezes em n − 1, logo x = 2 e não há nada a resolver.

   $$\text{fib}:x^2=x+1\Rightarrow \phi =1.6180340;\text{hanoi}:C(n)=1+2C(n-1)\Rightarrow x=2$$

4. Confirme em vez de acreditar. Ponha n em 29, leia o cartão das chamadas efetuadas, ponha n em 30, leia-o outra vez e divida. As escadas dão 1,83929, Fibonacci 1,61803 e Hanói exatamente 2. Cinco casas decimais nas três.

   $$\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. O que a raiz não dá é a contagem. 1,8393²⁰ é 196.331 enquanto o cartão marca 128.287, pelo que existe um fator de 0,65 à frente; as chamadas de Hanói são exatamente 2ⁿ⁺¹ − 1, um fator de 2. Os casos-base fixam essa constante e a recorrência fixa a raiz, e só a raiz decide quem ganha a longo prazo.

   $$1.8393^{20}=196,331\text{against}128,287⟹A=0.6534;\text{hanoi}:C(n)=2^{n+1}-1,A=2$$

6. O longo prazo chega depressa aqui. Em n = 20 Hanói faz 16,3 vezes mais chamadas do que as escadas, e em n = 30 faz 37,8 vezes mais. A razão duplica a cada 8,3 passos, uma vez que ln 2 a dividir por ln(2 ÷ 1,8393) dá 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$$