O código abaixo calcula os números de Fibonacci por umexponencialmente lento algoritmo:

#include <cstdlib>
#include <iostream>

#define DEBUG(var) { std::cout << #var << ": " << (var) << std::endl; }

constexpr auto fib(const size_t n) -> long long
{
    return n < 2 ? 1: fib(n - 1) + fib(n - 2);
}

int main(int argc, char *argv[])
{
    const long long fib91 = fib(91);

    DEBUG( fib91 );
    DEBUG( fib(45) );

    return EXIT_SUCCESS;
}

E estou calculando o 45º número de Fibonacci em tempo de execução e o 91º em tempo de compilação.

O fato interessante é que o GCC 4.9 compila o código e calculafib91 em uma fração de segundo, mas leva um tempo para cuspirfib(45).

Minha pergunta: se o GCC é inteligente o suficiente para otimizarfib(91) computação e não seguir o caminho exponencialmente lento, o que o impede de fazer o mesmo porfib(45)?

O GCC acima significa que produz duas versões compiladas dofib função onde um é rápido e o outro exponencialmente lento?

A questão énão como o compilador otimizafib(91) cálculo (sim! Ele usa uma espécie de memorização), mas se souber otimizar ofib função, por que não faz o mesmo parafib(45)? E, existem duas compilações separadas dofib função? Um lento e o outro rápido?