2

Fiz um programa com recursividade, porém quando o usuário digita 50, o processamento para gerar a sequência Fibonacci já passa ficar extremamente lento.

Será que é devido ao processamento de entrada/saída de dados no console? Existe um modo que seja mais rápido em Java, sem ser Scanner, BuffererReader ou OutputStream?

CÓDIGO: subclasse:

package Fib;

public class Fibonacci {
    public int calculaFibonacci(int n) {  
           if (n == 0)  
              return 0;  
           if (n == 1)  
              return 1;  
           return calculaFibonacci(n-1) + calculaFibonacci(n-2);  
    }
}

ClassePrincipal:

package TesteFibo;

import java.util.Scanner;

import Fib.Fibonacci;

public class chamaFibo {
    public static void main(String[] args){ 

        Scanner sc = new Scanner(System.in);
        System.out.println("Enter one number integer:");
        int tes = sc.nextInt();
        System.out.println();


        Fibonacci fibo = new Fibonacci();
        int i = fibo.calculaFibonacci(tes);
        //System.out.println(i);
        System.out.println("Fibonacci number: ");
        System.out.println(i);


        sc.close();
        }
    }

inserir a descrição da imagem aqui

5
  • 1
    Troque a imagem pelo código por favor
    – novic
    Commented 28/03/2019 às 14:12
  • Como o @VirgilioNovic disse, coloque o código na pergunta e não um print da sua tela. Existe a opção de editar a pergunta e inserir o código.
    – renanvm
    Commented 28/03/2019 às 14:14
  • 1
    Sim, desculpem. Já postei :) Obrigada.
    – Lamick
    Commented 28/03/2019 às 14:16
  • O problema não é a saída de dados, e sim a própria recursão: stackoverflow.com/a/21710949 / stackoverflow.com/q/49052327
    – hkotsubo
    Commented 28/03/2019 às 14:23
  • Hmmmm ... Vou mudar a recursividade e testar, kkk obrigada.
    – Lamick
    Commented 28/03/2019 às 14:26

1 Resposta 1

1

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 :

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.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .