Fibonacci algoritmo recursivo rendimientos resultado interesante

Question

Después de escribir un programa en Java para generar los números de Fibonacci utilizando un algoritmo recursivo, me di cuenta de que el aumento de tiempo en cada iteración es de aproximadamente $\Phi$ veces mayor que el anterior.

$\Phi$ es la Proporción áurea, su valor es de aproximadamente $1.61803398$ y está muy estrechamente relacionado con la serie de Fibonacci.

Aquí es un registro de salida desde el programa muestra el número de la iteración, el valor y el tiempo que se tomó para calcular:
30: 832040, calc time: 0.00s, took 1.33333x longer than previous. 31: 1346269, calc time: 0.01s, took 1.50000x longer than previous. 32: 2178309, calc time: 0.01s, took 1.66667x longer than previous. 33: 3524578, calc time: 0.02s, took 1.80000x longer than previous. 34: 5702887, calc time: 0.03s, took 1.55556x longer than previous. 35: 9227465, calc time: 0.05s, took 1.75000x longer than previous. 36: 14930352, calc time: 0.08s, took 1.57143x longer than previous. 37: 24157817, calc time: 0.13s, took 1.66234x longer than previous. 38: 39088169, calc time: 0.21s, took 1.60938x longer than previous. 39: 63245986, calc time: 0.31s, took 1.48544x longer than previous. 40: 102334155, calc time: 0.50s, took 1.63399x longer than previous. 41: 165580141, calc time: 0.80s, took 1.60800x longer than previous. 42: 267914296, calc time: 1.30s, took 1.62065x longer than previous. 43: 433494437, calc time: 2.15s, took 1.65004x longer than previous. 44: 701408733, calc time: 3.47s, took 1.61395x longer than previous. 45: 1134903170, calc time: 5.80s, took 1.67205x longer than previous. 46: 1836311903, calc time: 9.03s, took 1.55619x longer than previous.
Me he saltado los valores anteriores como el tiempo era demasiado corto para dar una diferencia.
No, definitivamente, no parece haber una relación entre ese momento y $\Phi$,
No pude encontrar ninguna información que explica por qué esto es así.

Aquí está el algoritmo utilizado, se obtiene simplemente los dos valores anteriores de la misma hasta que se obtiene para el comienzo de la serie:
function fib(number) { if (number == 0) return 0; if (number == 1) return 1; if (number > 1) return fib(number - 2) + fib(number - 1); }
Hay una explicación de por qué está pasando esto?

Answer 1

La función nfib que devuelve el número de llamadas de fib (que es aproximadamente lineal con el tiempo de ejecución) está siguiendo un similar esquema recursivo. Puedes terminar con un similar comportamiento el crecimiento. Véase también A001595.

nfib(0) = 1
nfib(1) = 1
nfib(n) = 1 + nfib(n-1) + nfib(n-2)

nfib: 1, 1, 3, 5, 9, 15, 25, 41, 67, ..
 fib: 0, 1, 1, 2, 3,  5,  8, 13, 21, 34, .. 

El uso de

$$ \mathtt{nfib}(n) = 2 \, \mathtt{fib}(n+1) - 1 $$

one sees that $O(\mathtt{nfib}) = O(\mathtt{fib})$.

Answer 2

Tenga en cuenta que usted no está utilizando un algoritmo óptimo para calcular sus números de Fibonacci. Porque es recursiva que calcula todos los números anteriores de nuevo.

Suponga $f(n)$ toma tiempo $\approx t_n$, para calcular el número. A continuación, $f(n+1)$ toma tiempo $\approx t_n+t_{n-1}$. De esta manera se sigue la misma relación, como los números de Fibonacci sí mismos.

La medición de la relación de la diferencia de tiempo es el mismo como el cálculo de la relación de $$\frac{f(n+1)}{f(n)}$$

y esto es lo que se sabe de enfoque

$$\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\cdots$$

como $n \to \infty$.