Langage C

Remarquons que si fibo1(n-1, tab, index) est calculée, alors fibo(n-2, tab, index) est connue. Le résultat peut s'écrire :

Une séquence d'initialisation sera nécessaire avant l'appel principal :

  tab[0]=1;

  tab[1]=1;  /* les valeurs connues */

  indice=1;  /* l'index précisant les valeurs déjà renseignées dans le tableau*/

  ... fibo1(n,tab,&indice);

À chaque appel, si pour n la valeur est connue, on retourne de la valeur stockée. Dans le cas contraire, on prépare le calcul du terme t_n en évaluant le terme précédant t_n-1, par appel récursif que l'on sommera avec la valeur du terme t_n-2 qui sera connue puisque nécessaire au calcul de t_n-1.

Nous aurons donc une suite d'appels récursifs : fibo1(n...), fibo1(n-1...), ... , fibo1(1...), suivie d'une remontée qui réalise les additions et l'affectation de tab[2], tab[3], ..., tab[n].

Nous avons réduit la complexité (n appels), mais avec une perte de place due au tableau.

L'étude de cette fonction nous amène à plusieurs constats :

• Les appels récursifs sont tels que l'exécution de la clause sinon de fibo1(2, ...) démarre véritablement, une fois fibo1(1, ...) évaluée, de même pour fibo1(i, ...) et fibo1(i-1, ...).

• Le 1^er paramètre n'intervient pas directement dans le calcul des valeurs successives.

• Ce 1^er paramètre sert principalement de compteur de n à 0, en sachant que les valeurs pour 0 et 1 sont connues.

• La valeur de l'indice de l'élément maximal connu évolue en fonction des calculs réalisés : fibo1(i, ...) le met à jour une fois le calcul effectué. Le 1^er point nous permet de préciser que cette évolution va de 2 à n.

• On peut exprimer explicitement l'ordre d'évaluation en utilisant l'appel récursif pour passer au calcul suivant :

  Index servira à connaître la position dans le tableau de la valeur devant être calculée,

  L'appel est réalisé après le calcul et une fois la valeur enregistrée dans le tableau.

• Seules les deux dernières valeurs du tableau sont utiles pour poursuivre le calcul.