Théorie 3.3, ajout: pourquoi Fibonacci naïf est exponentiel #

Fibonacci efficace #

public MonFibonacci calculerFib(int n){

    MonFibonacci resultat = new MonFibonacci();

    if(n == 0){

        resultat.setReponse(0L);

    }else if(n == 1){

        MonFibonacci moinsUn = calculerFib(0);

        resultat.setReponse(1L);
        resultat.setMoinsUn(moinsUn);

    }else{

        MonFibonacci moinsUn = calculerFib(n-1);

        MonFibonacci moinsDeux = moinsUn.getMoinsUn(); // la clé est ici

        resultat.setReponse(moinsUn.getReponse() + moinsDeux.getReponse());

        resultat.setMoinsUn(moinsUn);
        resultat.setMoinsDeux(moinsDeux);

    }

    return resultat;
}

Ça nous donnes des graphes comme:

calculerFib(0)
calculerFib(1)
calculerFib(2)
calculerFib(3)

Fibonacci naïf #

public long fib(int n){
    long reponse;

    if(n == 0){

        reponse = 0L;

    }else if(n == 1){

        reponse = 1L;

    }else{

        reponse = fib(n-1) + fib(n-2);

    }

    return reponse;
}

Ou encore:

public MonFibonacci calculerFib(int n){

    MonFibonacci resultat = new MonFibonacci();

    if(n == 0){

        resultat.setReponse(0L);

    }else if(n == 1){

        MonFibonacci moinsUn = calculerFib(0);

        resultat.setReponse(1L);
        resultat.setMoinsUn(moinsUn);

    }else{

        MonFibonacci moinsUn = calculerFib(n-1);

        MonFibonacci moinsDeux = calculerFib(n-2); // 2ième appel récursif!

        resultat.setReponse(moinsUn.getReponse() + moinsDeux.getReponse());

        resultat.setMoinsUn(moinsUn);
        resultat.setMoinsDeux(moinsDeux);

    }

    return resultat;
}

Dans les deux cas, le problème est qu’on fait deux appels récursifs à chaque fois.

n=2: 2 appels récursifs
n=3: 4 appels récursifs
n=4: 8 appels récursifs
n=5: 16 appels récursifs
n=6: 32 appels récursifs
etc.

Ce qui nous donnerait plutôt des graphes comme:

calculerFib(0)
calculerFib(1)
calculerFib(2)
calculerFib(3)
calculerFib(4)
calculerFib(5)
calculerFib(6)
…
calculerFib(10)