Récursivité terminale avec pile

Version imprimable

11/11/2016, 18h11
pbigen

Récursivité terminale avec pile

bonjour,
j'ai écrit en C la fonction fibonacci récursive : f(0) = f(1) = 0; f(n+2) = f(n+1)+f(n).

Je sais aussi le faire de manière itérative mais je sèche sur l'énoncé suivant utilisant une pile (j'ai compris la pile, et je sais l'utiliser) :

Citation:

Dérécursivez la fonction fibonacci en utilisant une pile. Indication: la pile va contenir les valeurs de n non encore calculées. Vous pouvez utiliser une variable resultat qui s'incrémente chaque fois que la pile contient 0 ou 1" (indices initiaux pour lesquels la fonction/suite est définie).

Avez vous des pistes pour me débloquer s'il vous plait ?
Merci d'avance.

Bonjour,

Citation:

Envoyé par pbigen

bonjour,
j'ai écrit en C la fonction fibonacci récursive : f(0) = f(1) = 0; f(n+2) = f(n+1)+f(n).
Je sais aussi le faire de manière itérative mais je sèche sur l'énoncé suivant utilisant une pile (j'ai compris la pile, et je sais l'utiliser) :
Avez vous des pistes pour me débloquer s'il vous plait ?
Merci d'avance.

Pour commencer, la récursivité terminale n’est pas la même chose qu’une dérécursivité ou récursivité normale. Je m’explique, la récursivité est dite terminale si seulement la valeur retournée par l'algorithme est constante (c'est-à-dire une valeur fixe ou calculé). De ce fait l’algorithme de Fibonacci dans votre exemple n’est pas un algorithme récursivité terminale tout simplement parce qu'un algorithme récusrisif terminal est l’équivalent d’une boucle itérative "tant que" mais possède la même complexité qu’une récursivité normale. La dérécursivé quant à elle, est le fait de transformer un algorithme récursif normal sous la forme récursivité terminale.
Pour faire simple, il faut transformer l’algorithme de Fibonacci en dérécursif ce qui donne ceci:
Code:

1 2 3 4 5 6 7 8 long f_der_fibo( long x, long y ){ if( x == 0 ) return y; if( x == 1 ) return y+1; return f_der_fibo( x-1, f_der_fibo( x-2, y) ); }
Attention, le code source-ci dessous peut comporter des erreurs.
Attention à la fonction dérécursive "f_der_fibo". la variable "y "peut fausser le calcule. Cette fonction doit être soumise à une vérification ou correction éventuelle avant sont emplois cas contraire il est toujours possible d'utiliser la version normale pour vérifier les résultats.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 #define MAXPILE 10 #include <stdio.h> #include <stdlib.h> long l_index; long l_pile[MAXPILE]; long l_pile_ret[MAXPILE]; long f_depiler( void ){ return l_pile[--l_index]; } void f_empiler( long val ){ l_pile[l_index++] = val; } long f_estVide( void ){ return !l_index; } long f_fibo( long x ){ if( 2 >= x ) return 1; else return f_fibo(x-1)+f_fibo(x-2); } /* * Attention à la fonction notamment * la variable y qui peut fausser le calcule */ long f_der_fibo( long x, long y ){ if( x == 0 ) return y; if( x == 1 ) return y+1; return f_der_fibo( x-1, f_der_fibo( x-2, y) ); } void f_print_pile( const long pile[MAXPILE] ){ long i = 0; for( i = 0; i < 10; i++ ) fprintf( stdout, "\t%ld", pile[i] ); fprintf( stdout, "\n" ); } int f_isPair( const int i ){ return ( i %2 ) ? 0: 1; } int main( void ){ unsigned int i = 0; unsigned int j = 0; /* valeur 0 ou 1 */ for( i = 0, j = 2; i < 10; i++, j = j+2 ) f_empiler( j ); f_print_pile(l_pile); for( i = 0; i < 10; i++ ) l_pile_ret[i] = f_der_fibo( f_depiler(), f_isPair(i) ); /* Teste correction avec la fonction fibo */ /*for( i = 0; i < 10; i++ ) l_pile_ret[i] = f_fibo(f_depiler());*/ if( !f_estVide() ){ fprintf( stdout, "Pas vide voicie le resultat\n" ); for( i = 0; i < 10; i++ ){ fprintf( stdout, "Fibo(%ld)\t=%ld\n", f_depiler(), l_pile_ret[i] ); } }else{ fprintf( stdout, "Liste vide réactualisation liste...\n" ); for( i = 0, j = 2; i < 10; i++, j = j+2 ) f_empiler( j ); fprintf( stdout, "Pas vide voicie le resultat\n" ); for( i = 0; i < 10; i++ ){ fprintf( stdout, "Fibo(%00ld)\t=\t%00ld\n", f_depiler(), l_pile_ret[i] ); } } return EXIT_SUCCESS; }
à bientôt

12/11/2016, 20h57
Médinoc

Citation:

Envoyé par sambia39

la récursivité est dite terminale si seulement la valeur retournée par l'algorithme est constante (c'est-à-dire une valeur fixe ou calculé).

J'ai du mal à comprendre cette définition.

Pour moi, une récursivité est terminale quand le retour du niveau courant est tout simplement le retour du niveau inférieur, avec aucun calcul entre (en gros, une fonction où l'on peut faire return maFonctionRecursive( ... );). Et l'avantage est qu'elle est triviale à transformer en boucle itérative, au point que la plupart des compilateurs sachent le faire (bien que rien dans la norme ne le garantisse).

Bonsoir

Citation:

Envoyé par Médinoc

J'ai du mal à comprendre cette définition.

Pour moi, une récursivité est terminale quand le retour du niveau courant est tout simplement le retour du niveau inférieur, avec aucun calcul entre (en gros, une fonction où l'on peut faire return maFonctionRecursive( ... );). Et l'avantage est qu'elle est triviale à transformer en boucle itérative, au point que la plupart des compilateurs sachent le faire (bien que rien dans la norme ne le garantisse).

Désoler si je n’ai pas été clair , Quand j’ai dit "La récursivité est dite terminale si seulement la valeur retournée par l'algorithme est constante (c'est-à-dire une valeur fixe ou calculé). Cela voulait effectivement dire que la valeur retournée par l’appel de la fonction est directement la valeur que l’on obtient par un appel récursif, sans qu'il n'y ait aucune opération sur la valeur en questions donc pas de calcul entre l’appel récursif et l’instruction return Exemple: L’algorithme récursif de la liste de Fibonacci.
Algorithme récursif de la liste de Fibonacci.
Code:

1 2 3 4 5 6 7 long f_fibo( long x ){ if( 2 >= x ) return 1; else return f_fibo(x-1)+f_fibo(x-2); }
Algorithme récursif terminale de la liste de Fibonacci
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 /* * Attention à la fonction notamment * la variable y qui peut fausser le calcule */ long f_der_fibo( long x, long y ){ if( x == 0 ) return y; if( x == 1 ) return y+1; /* * La valeur retournée par cet algorithme * est une valeur fixe, ou une valeur calculée */ return f_der_fibo( x-1, f_der_fibo( x-2, y) ); }
Au niveau de la condition "sinon" (cas récursif) avant de retourner le résultat, on effectue une opération. Donc le résultat à ce niveau n’est plus constant, mais calculé avant d'être retourné. Dans le second exemple on rend l’algorithme dérécursif (c’est-à-dire que l’on va la transformer en algorithme récursif terminal) et la valeur retournée par cet algorithme est une valeur fixe, ou une valeur calculée par Cet algorithme en question (c’est-à-dire que la valeur retournée par cet algorithme est directement la valeur obtenue par un appel récursif, sans qu'il n'y ait aucune opération sur la valeur) contrairement à la précédente d'où ma réponse "La récursivité est dite terminale si seulement la valeur retournée par l'algorithme est constante (c'est-à-dire une valeur fixe ou calculée)".

Cependant, je n’ai pas été précis quand j’ai écrit "Il faut transformer l’algorithme de Fibonacci en dérécursif", je l’admets (pour simplifier), j’ai dû présenter les faits sous cet angle, mais en réalité on ne peut pas dérécursiver de manière complète l’algorithme de Fibonacci, car celui-ci est multirécursif, mais on va la dérécursiver partiellement ou a moitié en usant d'un paramètre dit paramètre de cumul et le paramètre "y" joue ce rôle. Pour faire simple, elle permet a l’algorithme de devenir "si je peux dire" un algorithme récursif terminal, car pour rendre un algorithme récursif en algorithme récursif terminal. il faudrait que la fonction "récursive" n’ait point besoin des appels précédents pour fournir un résultat d'où le paramètre "y" pour avoir le cumul. Bref il se fait tard et j'espère que j'ai apporté quelque précision.
à bientôt

Citation:

Envoyé par pbigen

f(0) = f(1) = 0; f(n+2) = f(n+1)+f(n).

Tu es sûr que f(1) = 0? :koi: :koi:

Sinon je pense que le pseudo code est celui ci :mrgreen:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
    Si n == 0 Alors
        retourner 0 
    Sinon Si n == 1 Alors
        retourner 1 // 0 ???
    Fin Si
 
    pile.vider()
    pile.empiler(n)
 
    result = 0
 
    Tant Que ( pile.non_vide() )
        value = pile.depiler()
 
//      Soit l'algo classique
        Si (value == 0) Alors
//          result += 0
        Sinon Si (value == 1) Alors
            result += 1 // 0 ???
        Sinon /*Si (value >= 2) Alors*/
            pile.empiler(value - 2);
            pile.empiler(value - 1);
        Fin Si
 
//      Soit un algo à tester
        Si (value > 2) Alors
            pile.empiler(value - 2);
            pile.empiler(value - 1);
        Sinon
            result += 1 // 0 ???
        Fin Si
    Fin Tant Que

13/11/2016, 10h33
Médinoc

Ce qui est bizarre aussi, c'est que dans le cas de la suite de fibonacci il y a deux appels récursifs, dont seul le dernier est terminal.
Mais il doit y avoir moyen d'en faire une vraie récursivité simple terminale, si on se base sur l'algorithme itératif...

(d'ailleurs, l'algo itératif emploie l'équivalent d'une file de taille 2, plutôt qu'une pile)
13/11/2016, 12h59
picodev
Bonjour,

une fonction récursive terminale est une fonction telle que tout appel récursif soit la dernière action de cette fonction = plus rien n'est fait (mis à part le return évidemment) après un appel récursif.

Un fibonacci récursif terminal :
Code:

1 2 3 4 5 6 7 8 9 10 11 int fib_tailrec(int n, int a, int b) { if (n==0) return a; if (n==1) return b; return fib_tailrec(n-1, b, a+b); } int fib(int n) { return fib_tailrec(n,0,1); }
@Sambia39 : ta fonction n'est pas récursive terminale car tu fais un appel récursif pour créer un paramètre utilisé dans un autre appel récursif → non terminal.
13/11/2016, 15h06
sambia39

Bonjour,

Citation:

Envoyé par picodev

@Sambia39 : ta fonction n'est pas récursive terminale car tu fais un appel récursif pour créer un paramètre utilisé dans un autre appel récursif → non terminal.

+1, :plusser:Exacte et bonne remarque sur le code source. Désolé de cette erreur