Dérécursification de la procédure de Fibonacci

Nous allons voir, pour commencer, un exemple simple de dérécursification. Nous allons prendre pour exemple la suite de Fibonacci, dont voici la définition :

f ( 1 ) =1

f ( 2 ) =1

f ( n ) = f ( n-1 ) + f ( n-2 ), pour tout entier naturel n strictement supérieur à 2.

Sa traduction en langage informatique nous donne :

function fibo_rec(n: integer): integer;
begin
 if (n < 3) then fibo_rec := 1
 else
 fibo_rec := fibo_rec(n - 1) + fibo_rec(n - 2);
end;
 

Pour transformer cette procédure récursive en une procédure itérative, nous devons d'abord regarder quelles sont les valeurs successives de cette suite :

1,1,2,3,5,8,13,21,34,55,...

D'après la définition, on voit que chaque terme de la suite est une somme de deux nombres (f(n-1) et f(n-2)).

Nous devons donc avoir deux variables dans notre procédure itérative. Nous allons les appeler n1 et n2. Ces deux nombres verront leur valeur s'incrémenter progressivement.

Essais et observations

1) On veut calculer f(3). n1=1, n2=1, donc f:=n1+n2=2;

2) On veut calculer f(4); n1=1; n2=2; f (4)=1+2=3

3) On veut calculer f(5) : n1=2; n2=3; f(5)=2+3=5

Pour une valeur quelconque x, f(x)=n1+n2; il faut donc faire une boucle dans laquelle nous allons modifier progressivement les valeurs de n1 et n2.

Ainsi pour le cas 1) ci-dessus, on a algorithmiquement :

n1=1; n2=1; f:=n1+n2=2

Pour le cas 2) ci-dessus on a algorithmiquement:

n1=1; n2=1; //--- valeurs de base

aux:=n2; //--- sauvegarde de la valeur de n2

n2:=n1+n2=2; //--- calcul de f(n-1)+f(n-2)

n1:=aux=1; //--- nouvelle valeur de n1, correspondant à l'ancienne valeur de n2 avant la modif de la ligne du dessus

f:=n1+n2=3

Pour le cas 3) ci-dessus on a :

n1=1; n2=1; //--- valeurs de base

aux:=n2; //--- sauvegarde de la valeur de n2

n2:=n1+n2=2; //--- calcul de f(3)=f(2)+f(1)

n1:=aux=1; //--- nouvelle valeur de n1, correspondant à l'ancienne valeur de n2 avant la modif de la ligne du dessus

aux:=n2; //--- sauvegarde de la valeur de n2

n2:=n1+n2=3; //--- calcul de f(4)=f(3)+f(2)

n1:=aux=2; //--- nouvelle valeur de n1, correspondant à l'ancienne valeur de n2 avant la modif de la ligne du dessus

f:=n1+n2=5

On remarque que le groupe de 3 lignes peut très bien constituer une boucle répétée deux fois. Donc on peut la généraliser x fois si nécessaire; dans ce cas nous obtenons le programme suivant :

function fibo_it(n: integer): integer;
var i, aux, n1, n2: integer;
begin
 n1 := 1; n2 := 1;
 for i := 3 to 10 do
 begin
 aux := n1 + n2;
 n1 := n2;
 n2 := aux;
 end;
 fibo_it := aux;
end;
 

Comme on peut le constater, la dérécursification est parfois très simple, elle revient à écrire une boucle, à condition d'avoir bien fait attention à l'évolution des variables au cours de l'exécution. Mais parfois elle est extrêmement difficile à mettre en oeuvre, comme c'est le cas pour certaines fractales ou les tours de Hanoï.

Télécharger le code source Delphi