PrEDA: cálculo empírico del coste temporal de Fibonacci

Continuando con post anteriores sobre esquemas algorítmicos. Dejo aquí unas pruebas empíricas sobre cómo calcular el Número de Fibonacci de números grandes. Si vemos la definición de Fibonacci es la siguiente:

Fibonacci(n) = 1, si n=0 o n=1
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2), si n> 1

El código en PHP para resolverlo sería el siguiente:

function fibonacciRecursive($n)
{
    if ($n <= 1) {
        return 1;
    } else {
        return fibonacciRecursive($n - 1) + fibonacciRecursive($n - 2);
    }
}

Observamos que se repiten cálculos, con lo que aplicando programación dinámica tenemos el siguiente código:

function fibonacciDynamic($n)
{
    $tabla = array();

    if ($n <= 1) {
        return 1;
    } else {
        $tabla[0] = $tabla[1] = 1;

        for ($i = 2; $i <= $n; ++$i) {
            $tabla[$i] = $tabla[$i - 1] + $tabla[$i - 2];
        }

        return $tabla[$n];
    }
}

Estas dos funciones, para compararlas empíricamente, las usamos en un bucle que vaya incrementando el número $n para obtener su coste temporal empírico. También en PHP con éste código:

define('MAX_N', 100);

for ($i = 0; $i <= MAX_N; ++$i) {
    $timeStart = microtime(true);
    $theNumber = fibonacciRecursive($i);
    //echo 'fibonacciRecursive('.$i.') = '.$theNumber.PHP_EOL;
    $timeEnd = microtime(true);
    echo 'RECURSIVE fibonacci('.$i.'): Calculated in '.number_format($timeEnd - $timeStart, 9).' seconds.'.PHP_EOL;

    $timeStart = microtime(true);
    $theNumber = fibonacciDynamic($i);
    //echo 'fibonacciDynamic('.$i.') = '.$theNumber.PHP_EOL;
    $timeEnd = microtime(true);
    echo '  DYNAMIC fibonacci('.$i.'): Calculated in '.number_format($timeEnd - $timeStart, 9).' seconds.'.PHP_EOL;
}

Ahora bien, ejecutamos todo junto. Así podemos ver cómo, para números grandes, se convierte en imposible resolver el Número de Fibonacci con programación recursiva:

RECURSIVE fibonacci(22): Calculated in 0.002473116 seconds.
  DYNAMIC fibonacci(22): Calculated in 0.000002861 seconds.
RECURSIVE fibonacci(23): Calculated in 0.004077911 seconds.
  DYNAMIC fibonacci(23): Calculated in 0.000005007 seconds.
RECURSIVE fibonacci(24): Calculated in 0.006484985 seconds.
  DYNAMIC fibonacci(24): Calculated in 0.000003815 seconds.
RECURSIVE fibonacci(25): Calculated in 0.010952950 seconds.
  DYNAMIC fibonacci(25): Calculated in 0.000016928 seconds.
RECURSIVE fibonacci(26): Calculated in 0.017073154 seconds.
  DYNAMIC fibonacci(26): Calculated in 0.000005960 seconds.
RECURSIVE fibonacci(27): Calculated in 0.027941942 seconds.
  DYNAMIC fibonacci(27): Calculated in 0.000008106 seconds.
RECURSIVE fibonacci(28): Calculated in 0.045236111 seconds.
  DYNAMIC fibonacci(28): Calculated in 0.000008106 seconds.
RECURSIVE fibonacci(29): Calculated in 0.073548079 seconds.
  DYNAMIC fibonacci(29): Calculated in 0.000009060 seconds.
RECURSIVE fibonacci(30): Calculated in 0.118798018 seconds.
  DYNAMIC fibonacci(30): Calculated in 0.000012159 seconds.
RECURSIVE fibonacci(31): Calculated in 0.202280998 seconds.
  DYNAMIC fibonacci(31): Calculated in 0.000010967 seconds.
RECURSIVE fibonacci(32): Calculated in 0.310992002 seconds.
  DYNAMIC fibonacci(32): Calculated in 0.000011921 seconds.
RECURSIVE fibonacci(33): Calculated in 0.506221056 seconds.
  DYNAMIC fibonacci(33): Calculated in 0.000011921 seconds.
RECURSIVE fibonacci(34): Calculated in 0.834569931 seconds.
  DYNAMIC fibonacci(34): Calculated in 0.000009060 seconds.
RECURSIVE fibonacci(35): Calculated in 1.305525780 seconds.
  DYNAMIC fibonacci(35): Calculated in 0.000010014 seconds.
RECURSIVE fibonacci(36): Calculated in 2.117379189 seconds.
  DYNAMIC fibonacci(36): Calculated in 0.000010014 seconds.
RECURSIVE fibonacci(37): Calculated in 3.495128870 seconds.
  DYNAMIC fibonacci(37): Calculated in 0.000009060 seconds.
RECURSIVE fibonacci(38): Calculated in 5.618491888 seconds.
  DYNAMIC fibonacci(38): Calculated in 0.000010014 seconds.
RECURSIVE fibonacci(39): Calculated in 9.390465975 seconds.
  DYNAMIC fibonacci(39): Calculated in 0.000010014 seconds.
RECURSIVE fibonacci(40): Calculated in 14.963202953 seconds.
  DYNAMIC fibonacci(40): Calculated in 0.000010014 seconds.

La función Fibonacci recursiva, crece exponencialmente, mientras que la dinámica es lineal. Es decir, que más nos vale usar la función de programación dinámica.