Discussion :

[miltone]

Bonsoir à tous,

Je débute en programmation et je me suis lancé dans l'étude du langage algorithme.J'ai donc étudié l'écriture d'algorithme très simple, les structures de contrôles(les boucles et les conditionnelles)et les fonctions.

J'ai un peu de mal à concevoir les fonctions à récursivité terminale.Pourtant les récursives simples pas de problème j'ai compris, mais les terminales beaucoup moins.

Pourriez-vous m'éclairez sur point de façon simple ?


J'ai créé des notes sous open office du bouquin d'ou je tire mon enseignement, si vous souhaité je peux vous les envoyer ou vous les montrer mais je ne sais pas comment faire...

Merci à vous de votre Précieuse aide

[gorgonite]

la récursivité terminale signifie juste que tu n'empiles pas les appels

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
algo non-terminal
fact N = 
si N = 0 
  alors 0
  sinon N * fact  (N-1)


algo terminal
fact-auxiliaire N accu = 
si N = 0 
  alors accu
  sinon fact-auxiliaire (N-1) (N*accu)

fact N = fact-auxiliaire N 1

comprends-tu ?

[miltone]

Je comprend les principes de tes algorithmes mais pas les détails.
J'ai du mal à comprendre ton écriture qui est très certainement du à mon manque d'expérience.

Tu me dit que la récursivité terminale a des appels qui ne s'empilent pas pourtant la fonction lance bien plusieurs appels à la suite comme pour calculer U8 dans la suite de fibonacci. D'où mon incompréhension car les 2 récursivités lance chacun plusieurs appels de la même fonction(avec bien entendu des paramètres différents).

[Jedai]

Ce qu'on appelle récursivité terminale, c'est une fonction récursive qui renvoie la valeur de retour d'un appel de fonction directement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
function f (x) :
  y = blabla
  return g(y)
end

Autrement dit f() fait ses petits calculs, puis elle appelle une autre fonction g() et elle renvoie la valeur retournée par g()... On s'aperçoit alors qu'il n'est pas nécessaire de passer par cette étape intermédiaire, qu'à partir du moment où on a appelé g(), f() n'est plus nécessaire, on peut donc au lieu d'appeler g() dans f, remplacer f() par g() à cet instant et on obtiendra le même résultat final.

Ensuite pour comprendre pourquoi c'est important et en quoi c'est une grosse optimisation, il faut comprendre comment fonctionne l'appel de fonction dans un langage à pile (comme pratiquement tous les langages actuels), est-ce ton cas ?

--
Jedaï

[GnuVince]

Je l'ai déjà expliqué souvent, mais je m'ennuie, donc je vais le refaire.

Je vais utiliser le langage JavaScript pour cet exemple. Nous allons implémenter une fonction d'addition récursive et récursive terminale.

Voici la version récursive:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
function ajouter(x, y) {
  if (y == 0)
    return x;
  else
    return 1 + ajouter(x, y-1);
}

Voici son développement quand on l'appelle avec 4 et 3:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
ajouter(4, 3);
1 + ajouter(4, 2);
1 + (1 + ajouter(4, 1));
1 + (1 + (1 + ajouter(4, 0)));
1 + (1 + (1 + 4));
1 + (1 + 5);
1 + 6;
7

On peut voit que les appels à 1 + sont gardés sur le stack en attendant que ajout aie une valeur finale. On remarque aussi que lorsqu'on arrive à y = 0, il reste encore du travail à faire.

Voici comment écrire la même fonction en récursif terminal:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
function ajouter(x, y) {
    if (y == 0)
        return x;
    else
        return ajouter(x + 1, y - 1);
}

Et le développement:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
ajouter(4, 3);
ajouter(5, 2);
ajouter(6, 1);
ajouter(7, 0);

On peut voir qu'il y a moins d'étapes à faire, que le programme n'a pas besoin de garder les +1 sur le stack et que lorsqu'on arrive à y = 0, on a notre réponse.

J'espère que ça aide.

[Garulfo]

Le premier message indique que le problème de notre ami vient de la conception. Si c'est bien ça, je te rassure tout de suite, écrire une fonction de forme récursive terminale est aussi difficile que d'écrire une boucle itérative.
En fait s'en est une. Et si tu ne t'en rends pas compte directement, ne t'inquiètes pas non plus, car les techniques pour optimiser automatiquement un appel de fonction de forme récursive terminale en processus itératif n'est que récent aussi. Ce n'est pas simple.

Ce n'est d'ailleurs pas optimisé dans tous les langages. La plupart des langages fonctionnels le font vu que c'est théoriquement le seul moyen « fonctionnel » de faire des boucles. Mais pour les autres c'est rarement le cas je pense.

[miltone]

Bonjour à vous,

Jedai:
D'après ce que tu m'a dit je comprend que:
-une fonction récursive EMPILE bien des fonctions différentes puisque la 1e est mise en attente jusqu'a obtention du résultat demandé par ses fonctions enfants pour retourné son résultat à elle final.Ainsi la notion d'empilement est bien réel.

-une fonction récursive terminale quant à elle intégre directement dans l'appel d'une seconde fonction les données utiles de la première pour évité de la mettre en attente inutilement.

Est tu d'accord avec ma compréhension?

Sinon je n'est étudié pour le moment aucuns langage de programmation mais j'ai un schéma d'explication pour les fonction récursive, sur le fait qu'elles sont mise en attente, attendant la réponse de l'autre fonction pour finir.

Connais tu un moyen ou je puisse stocker des documents sur le net afin de les faires partager en temps voulu au autre(pour mes notes par exemple pour avoir une meilleur idée de mes intérrogations)?
---------------------------------------------------------------
GnuVince:

Super explication.Avec celle de Judai je pense avoir compris le principe.Mais a mon avis j'aurais un peu de mal a la mettre en pratique pour des choses plus compliqué mais on peut mettre ca sur le compte de l'expérience aussi je pense.
que signifie le terme "stack" ?
----------------------------------------------------------------
Garulfo:

J'ai remarqué effectivement qu'une récursivité terminale peut se transcrire en fonction itérative.D'ailleurs pour ma part je serais plus à l'aise à écrire itérativement que terminalement.
Quoique cela peut compliqué la mise en oeuvre du calcul dans le boucle...

[GnuVince]

miltone: le stack est l'endroit ou les appels de fonctions vont être empilés. "Stack" veut dire "pile" en anglais.

Et pour un certain nombre de fonctions récursives, faire une version récursive terminale est plutôt simple: tu dois simplement ajouter une variable accumulatrice dans laquelle tu vas mettre ton résultat.

[miltone]

Merci à vous de votre aide et de vos réponses.Je pense avoir mieux compris et maintenant il me faut en faire quelques unes pour que ca rentre...

J'attend les réponses Garuflo et Jedai si ils souhaitent rajouté quelques choses et je passe ce sujet en résolu

[Garulfo]

Garulfo:

J'ai remarqué effectivement qu'une récursivité terminale peut se transcrire en fonction itérative.D'ailleurs pour ma part je serais plus à l'aise à écrire itérativement que terminalement.
Quoique cela peut compliqué la mise en oeuvre du calcul dans le boucle...

C'est la même chose ! Par exemple en C

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
int deux_exposant (int n, int resultat)
{
    if (n == 0)
        return resultat ;
    else
        return deux_exposant (n-1, 2*resultat) ;
} // puis 2^n = deux_exposant(n, 1)

est la même chose que

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
// calcul de 2^n
int resultat = 1;
while ( n != 0 )
{
    resultat = 2 * resultat;
    n = n - 1;
}

La récursivité terminale n'est qu'une recopie de l'itération sous une autre forme. Chaque paramètre sert de registre. Si tu vois ta boucle et que tu l'écris proprement, tu as la forme récursive terminale. D'où la difficulté de conception équivalente que tu cherches la forme itérative ou récursive terminale. En effet, les formes récursifs sont parfois très aisées à obtenir: on ne parcourt pas un arbre en pensant itératif, mais récursif; on ne calcul pas une fractale de manière itératif... Dans ces cas, le passage à la forme récursive terminale est très difficile.

[miltone]

Je me suis donc essayer aux exercices...
Je dois écrire la suite de Fibonacci en récursivité terminale.
J'ai donc écris d'abord une fonction itérative, puis une fonction récursive simple mais je n'arrive pas à trouver une forme terminale.

Pourriez-vous m'indiquer une piste, une voie vers laquelle je puisse me dirigé pour écrire ce fichu algorithme?Car en recherchant sur le net des indices, je ne suis tombé que sur des exemples bien trop simples de récursivité terminale où finalement il n'y avait pas d'inconnus comme la suite de Fibonacci.

Je ne vois pas qu'elle variable créer qui pourrais s'incrémenter pour au final me donner le résultat.

voici mes fonctions déjà créer:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
Fonction fibonacciIteratif(nb : entier) : entier
Variables compteur, varPair, varImp, resultat nb : entier
Debut
        varPair <-- 0
        varImp <-- 1
        lire(nb);
        compteur <-- 2;
        tant_que(compteur < ou = nb ) alors
        {     
              resultat <-- varPair + varImp
              si (compteur MOD different de 0) alors
                       varImp <-- resultat
              sinon
                       varPair <-- resultat
              compteur <-- compteur + 1             
        }
        ecrire(resultat);
Fin
---------------------------------------------------------------
Fonction FibonacciRecursive(nb : entier) : entier
Debut
            si (n=0) alors
            retourne(0);
            sinon si (n=1) alors
            retourne(1);
            sinon 
            retourne(Fibonacci(nb-1) + Fibonacci(nb-2));
Fin

[GnuVince]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
def fib(n):
  return fib_aux(0, 1, n)

def fib_aux(a, b, n):
  if n == 0:
    return a
  else:
    return fib_aux(b, a+b, n-1)

À toi de la traduire dans le langage de ton choix.

[Garulfo]

Je me permet de modifier légèrement le code de GnuVince pour faire apparaître le lien

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
def fib(n):
  return fib_aux(0, 1, nb)

def fib_aux(varPair, varImp, compteur):
  if compteur == 0:
    return varPair
  else:
    return fib_aux(varImp, varPair+varImp, compteur-1)

[Garulfo]

Ah oui.. un truc intéressant aussi: la trace

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
fib(3)
fib_aux(0, 1, 3)
fib_aux(1, 1, 2)
fib_aux(1, 2, 1)
fib_aux(3, 1, 0)
-> 3

À comparer avec l'état des variables varPair et varImp du code de miltone. Ici le compteur se décremente au lieu de s'incrémenter.

[miltone]

Ah ok!!!

J'ai compris il suffit de joué avec les paramètres de la fonction qui se remplace aisément en fait.Effectivement dans ce cas cela deviens moins difficile d'en élaborer des fonctions terminales.

J'avais compris la théorie et maintenant j'ai saisi la pratique

Merci à vous pour votre précieuse aide Garulfo GnuVince Jedai et gorgonite

[Garulfo]

On oublie pas le ! Siouplait

[miltone]

C'était fait avant que tu réponde Garulfo

[Garulfo]

Non tu ne m'as pas compris...
Quand on a résolu un problème, tu mets le tag et tu changes le titre.

[miltone]

J'avais déjà appuyer sur le bouton "Résolu" et apparemment le titre de mon sujet à été modifié.Je ne sais pas si c'est automatique ou si c'est un modo qui la changé par contre ?

Mais c'est bien noté Garulfo la prochaine fois ca serais parfait