Problema real
Os algoritmos são completamente diferentes. Por isto quanto mais você executar ele fica pior.
Em C está chamando
fibo(num - 1) + fibo(num - 2)
Em Java está
fibo(num - 1) + (num - 2)
Coloquei no GitHub para referência futura.
O primeiro chama a mesma função duas vezes. O segundo apenas uma. Em Java nem dá o resultado certo. Portanto ele é muito pior que em C. Antes de um algoritmo ser mais rápido ele precisa estar correto.
VM + JITter X compilação tradicional
Rodar em VM não significa que o código seja interpretado. Pelo contrário, significa que o código pode ser otimizado de forma bastante agressiva no momento da execução. Através do JITter é possível produzir o melhor código nativo para aquela situação específica, para aquela plataforma específica. Ser possível não siginifica que acontece de fato.
Java pode estar usando alguma técnica de memoization.
Em C o compilador usa o mínimo denominador comum para poder rodar em qualquer lugar. Com pouca execução você pode estar inclusive tendo um gasto de tempo grande para a execução da compilação just in time. Conforme a execução do algoritmo vai se tornando predominante este tempo passar ser irrisório.
Benchmark
Você não passou dados que dê para avaliar bem.
Falta informações como foi compilado. Isto pode fazer uma diferença enorme em C que é uma linguagem que o programador precisa dizer como fazer tudo. Tem ferramentas para alcançar o máximo de velocidade mas se você não usá-las corretamente, pode ocorrer o oposto. Tem em grande chance de Java ter transformado o código recursivo em laço de repetição e em C isto não ter ocorrido. Isto faz uma diferença enorme. Esta provavelmente é a melhor explicação para haver uma diferença neste sentido. Mais ainda, o JITter pode ser mais agressivo quando ele detecta que o código é muito executado. Há casos que o máximo de otimização em C piora o resultado, por isto o compilador não decide sozinho.
Você não mostrou o ambiente em que isto isto está rodando. Isto pode, eventualmente, explicar parte da diferença em conjunção com outros fatores.
Não sabemos como foi medido o tempo. Você pode ter usado um método errado. Pode ter tido a interferência externa, pode não ter executado tentativas suficientes para obter um resultado confiável, pode não ter usado algo preciso para medir.
Sequer sabemos quantos números foram tentados no último teste. E não sabemos se algo maior produziria a mesma proporção.
Não é esquisito o C ir de 0 para 64 ms só triplicando a execução? Já é estranho o Java ter mais que triplicado o tempo quando triplica a exposição. O mais normal é ter uma redução. Estes números não fazem sentido mesmo com as explicações lógicas. Pode até ter uma explicação porque isto ocorre, mas no momento só posso dizer que não sei de tudo para avaliar se está correto. Certamente tem fatores extras atrapalhando a avaliação.
Uma possível explicação é o uso de casts implícitos. Eu não fiz teste, mas esta confusão de chamar a primeira vez um int
(este não deve causar muito problema) e as demais chamar com unsigned long
algo que espera long
como parâmetro reentrante pode afetar alguma coisa também. Ou seja, os algoritmos não são exatamente iguais.
Especulações
Por mais que possa parecer que o código seja o mesmo você não está comparando necessariamente de forma justa. Uma linguagem pode executar melhor que outra um código que se encaixe como uma luva para ela e não tão bem em outra. É comum algoritmos terem que ser modificados em outra linguagem para obter o melhor resultado. Isto é só especulação, não estou dizendo que é o caso, mas é uma possibilidade.
Não parece ser o caso, mas alocações de memória podem fazer diferença também. Por incrível que pareça o garbage collector pode fazer um programa ficar mais rápido que outro com memória gerenciada manualmente. Basta o programador não saber tirar o máximo disto. O gerenciamento manual pode ser a estratégia mais rápida. Mas só quando se faz da maneira correta. Isto pode fazer uma diferença tremenda em muitos casos. Ao contrário da crença popular, o GC costuma alocar memória de forma mais eficiente que a alocação individualizada. E muitos não percebem que não há desalocação alguma até que seja necessário reclamar memória. O GC é ruim quando ele pausa a aplicação para fazer a limpeza.
Também não parece ser o caso, mas existem casos que a execução efetiva realizada por bibliotecas escritas em C/C++, ou até mesmo assembly, por um programador muito experiente naquele domínio que produzirá um código melhor que o seu. No passado vi num site bem conhecido de (bechmark um código Java que executava absurdamente mais rápido que o mesmo código em C. Só que o código em Java chamava uma biblioteca escrita em assembly para fazer 99% do trabalho. Então a comparação era C contra assembly e não Java.
Em alguns casos uma mudança muito pequena como a inversão da lógica de um if
pode mudar dramaticamente para mais ou para menos em uma linguagem. E pode ocorrer o oposto em outra. Neste exemplo o uso do operador or
pode não ser a melhor opção para uma delas. Em outros casos o próprio uso do if
(branch costuma ser uma operação bem cara no processador) pode ser eliminado e fazer mais diferença em uma linguagem que outra.
Conclusão
Leia mais sobre as otimizações do Java.
Veja como as otimizações fazem uma diferença enorme em C. E principalmente note que o resultado deste teste não é parecido com o seu, mesmo que o código seja essencialmente o mesmo.
Quando for fazer o teste, execute várias vezes, elimine os melhores e piores resultados, faça uma média. Certifique-se que nada na máquina possa atrapalhar a execução do teste. Use medição do tempo de máquina e não o relógio. E lembre-se testar coisas que não demoram quase nada para saber qual é mais rápido não ajuda muito. Tudo que já é rápido o suficiente não precisa ser o mais rápido possível.
Tente fazer o teste com vários níveis de otimização em C. Experimente forçar o inline da função em C. Experimente desligar a checagem do stack, é mais fácil dar segurança sem a checagem, constante quando o compilador sabe quando está executando e C não tem essa chance.
Uma coisa isto também mostra que eu sempre falo. Recursão é algo superestimado. Experimente obter o mesmo resultado com um algoritmo de repetição.
Tente também fazer um pré-cálculo em ambos os casos. Você pode montar uma tabela de lookup e pegar os resultados prontos ao invés de calcular. Você troca um pouco de consumo extra de memória por melhor tempo de execução.