Conforme explicado nesta resposta, o problema é a recursão em si, e não a entrada e saída dos dados (até porque você só usa o Scanner
e o println
poucas vezes e fora da função recursiva, então eles não são a causa da lentidão). Inclusive, segue uma tradução/adaptação da explicação que tem lá:
Se F
for a sua função recursiva, chamar F(10)
faz o seguinte:
F(10) = F(9) + F(8)
F(10) = F(8) + F(7) + F(7) + F(6)
F(10) = F(7) + F(6) + F(6) + F(5) + F(6) + F(5) + F(5) + F(4)
....
Repare que F(8)
é calculada duas vezes, F(7)
3 vezes, e assim por diante. Quanto maior o número inicial, mais chamadas recursivas - e neste caso, redundantes - serão feitas, e isso cresce exponencialmente conforme o valor inicial.
Sem contar que todas essas chamadas ficam "penduradas", esperando o retorno das chamadas recursivas abaixo delas, até que se chegue em F(1)
e F(0)
(que é quando a função para de fazer novas chamadas recursivas e retorna um valor). Dependendo do valor inicial e da configuração da sua JVM, isso pode estourar o stack, gerando um StackOverflowError
.
Modifiquei suas funções para termos uma ideia do que acontece.
Criei um contador para vermos quantas chamadas são feitas para a função, e mudei os tipos de int
para long
, já que os resultados estavam estourando o valor máximo que um int
suporta (que é cerca de 2 bilhões):
public class Fib {
static long CONTADOR;
public static long calculaFibonacci(long n) {
CONTADOR++;
if (n == 0)
return 0;
if (n == 1)
return 1;
return calculaFibonacci(n - 1) + calculaFibonacci(n - 2);
}
public static void main(String[] args) {
CONTADOR = 0;
calculaFibonacci(50);
System.out.println(CONTADOR);
}
}
O resultado foi:
40730022147
Ou seja, mais de 40 bilhões de chamadas recursivas. Não é à toa que ficou lento.
Se calcularmos para 25, o resultado é:
242785
Ou seja, dobrando o número inicial (de 25 para 50), a quantidade de chamadas recursivas aumenta de 242 mil para mais 40 bilhões (de fato um aumento exponencial, como já explicado).
Por que não fazer sem recursão? Independente do número inicial, é apenas uma chamada de função com um loop simples. Esta é a solução que eu usaria (a menos que você esteja estudando recursão, claro).
public long fib(long n) {
long a = 0;
long b = 1;
long c = 1;
for (long i = 0; i < n; i++) {
a = b;
b = c;
c = a + b;
}
return a;
}
A complexidade deste algoritmo cresce linearmente - e não mais exponencialmente - de acordo com o valor inicial, sem contar que métodos iterativos são bem menos custosos se comparados aos recursivos.
Observações
- Se quiser, também é possível usar a recursão, porém guardando os resultados já computados (evitando assim que sejam recalculados), usando técnicas de memoization - o que já diminui bastante a quantidade de chamadas.
- Isso não quer dizer que
println
nunca causará problemas de desempenho. Na verdade, se você usá-lo dentro da função recursiva (para imprimir os valores intermediários, por exemplo), isso vai deixá-la mais lenta também. Mas neste caso específico, como o I/O é feito somente fora da função, não é a causa da lentidão.