Discussion :

[s-ehtp]

bonjour;
je tiens d'abord a vous remercier de ce site et les efforts que vous faites pour le faire reussir.
je viens de commencer ma premiere année en informatique.mais franchement la matiere dont j ai trouvé difficile est l'algorithme!.j'arrive pas a resoudre tous les exos qui cherche a traiter l'algorithme.
j ai besoin de votre aide!
en fait l exo que je vous suggere cé le calcul de terme general d une suite,un=un-2 +un-1,sachant u1 et u2 sont des données.
et merci d'avance

[Nemerle]

Ton algo doit-il être récursif ou "direct"?

En direct, avec u0=2 et u1=3 par exemple, on calcule u10:

Code :

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

1
2
3
4
5
6
7
8
9
10
entier a,b,c,n
a=2
b=3
n=10
pour i de 2 à 10 faire
   c=b
   b=b+a
   a=c
finpour
résultat: afficher b

[s-ehtp]

ce mot recursif,je l ai jamais entendu.en fait,on est seulement dans des initiation,on a fait,les fonctions repeter ..jusqu'a et tant que,bref les boucles.
je vous remercie infiniment pour ta reponse!! .mais ce que je me demande c est on a le droit de preciser ce n=10,c est a dire peut on pas le generaliser pour n..?
autre question,ce variable c represente quel terme de la suite?
ca serait tres gentil si vous m'expliquer ces etapes.
merci!!

[Nemerle]

C est une variable "tampon" qui te sert à stocker le précédent terme b pour le passer "en a".

T'as calculé u2,u3,u4 par exemple. T'as donc a=u3,b=u4.

Tu stockes u4 dans c: c=b
Et tu calcules u5: b=b+a (soit b=u4+u3)
Ensuite, tu remets u4 dans a: a=c

T'as donc maintenant a=u4, b=u5.

[s-ehtp]

mercii.j'ai compris.moi en fait j'ai fait un essai,je vous le suggere et vous me le corrrigez. (pardonnez moi je suis un peu lourde).bon mon essai le voila:
variables:n,ui,ui-1,ui-2 ,entier
repeter ecrire(entrer un entier) jusqua n superieur ou egale a 0(c est une controle de saisie)
lire(u1)
lire(u2)
pour i allant de 2 a n faire
ui=ui-1+ui-2
finpour
fin

[Jedai]

Tu n'as pas mis à jour les u(i-1) et u(i-2) à chaque itération de ta boucle.

Par ailleurs je te propose une autre manière de raisonner :
(en supposant que u1 = 18 et u2 = 26)

Code :

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

1
2
3
u 1 = 18
u 2 = 26
u n = u (n-1) + u (n-2)

Est-ce que tu comprends la notion de fonction ? Là j'ai défini une fonction u telle que (u n) donne le n-ème terme de ta suite. Comme tu le vois, mon code ressemble énormément à la définition mathématique de ta suite.

Je dois tout de même te prévenir que ce code est extrèmement innefficace, dans le même style mais en plus efficace, un programmeur écrirait plutôt :

Code :

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

1
2
3
4
auxiliaire 1 = (26,18)
auxiliaire n = let (un, un_1) = auxiliaire (n-1) in (un + un_1, un)
 
u n = let (_, un) = auxiliaire n in un

Mais c'est moins joli et il y a plus de détails à comprendre.

Au fait, où suis-tu ta formation en informatique ?

--
Jedaï

[s-ehtp]

en fait c est seulement 2 semaines que j ai commencé mes etudes.mais l algo que tu a ecrit,on l a pas encore abordé.c est pour cela que je me suis inscrit dans ce site pour que vous m'aider.
je suis un debutant,un vrai debutant.
et je suis mes etudes dans une ecole d'ingenieur apres mes classes preparatoires.donc c est mon premier contact avec l'algorithme.mais cela n'empeche de dire que je l ai trouvé difficile!
mais je vous remercie quand meme pour m'avoir repondu!

[Nemerle]

De rien. De quel pays es-tu?

[s-ehtp]

pardon mais pourquoi le i de 2 à 10 et non de 1 à 10?

[PRomu@ld]

Parce que u0 et u1 sont connus, le terme suivant à calculer est u2, jusqu'à u10. Or si tu fais i de 1 à 10 tu vas calculer u2 à ... u11.

[Sve@r]

ce mot recursif,je l ai jamais entendu

C'est une notion qui implique la mémorisation automatique par le système des éléments en attente du calcul suivant. Tu devrais pas tarder à l'apprendre

Exemple tu as une fonction somme(a, b) qui te renvoie a + b; et une fonction mult(a, b) qui te renvoie a * b

Tu demandes res=mult(somme(2, 3), 5) => pour avoir ton résultat, il faut que la fonction "mult" se mette en attente du calcul de la fonction somme(2, 3). une fois ce calcul fait, la fonction mult récupère ce résultat et peut le multiplier par 5.
Cette mise en attente est automatiquement faite par tous les langages actuels et t'as pas à t'en préoccuper.

Mais puisqu'une fonction X peut attendre un résultat donné par une fonction Y, rien n'empêche que la fonction Y soit la même fonction. C'est ce qu'on nomme "récursivité" => la fonction s'appelle elle-même encore et encore et jusqu'à ce qu'une condition de "fin de récursivité" soit atteinte (sinon il n'y aurait jamais de fin). Chaque appel est mis en attente du résultat donné par l'appel suivant. Une fois la condition atteinte, la fonction délivre son résultat à l'appel précédent qui délivre son résultat au précédent etc et chaque résultat remonte jusqu'au point de départ qui récupère le calcul final.

Un exemple classique est la fonction factorielle car factorielle(n) c'est n * factorielle(n -1). Donc la fonction dans les différents langages ressemble à ça

Code :

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

1
2
3
4
5
6
def factorielle(n)
debut
    si n vaut 0 => renvoyer 1      // Ca c'est la condition de fin de récursivité
 
   sinon renvoyer n * factorielle(n - 1)     // Ca c'est l'appel récursif
fin

L'équivalent en non-récursif

Code :

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

1
2
3
4
5
6
7
8
9
10
11
def factorielle(n)
debut
    resultat=1
    indice=1
    tant que indice <= n
    faire
         resultat=resultat * indice
         indice = indice + 1
    fin faire
    renvoyer résultat
fin

Comme tu vois, une fois qu'on a bien intégré le concept, une fonction récursive est souvent plus simple à écrire que son homologue non récursif... mais le problème est qu'elle charge énormément le système qui doit se charger lui-même de la mémorisation du contexte de travail de l'appel en cours pour se consacrer à l'appel suivant qui lui-même peut être mémorisé s'il y a encore un appel suivant etc.

Exemple pour ton exo sur fibonacci en récursif

Code :

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

1
2
3
4
5
def fib(n)
debut
     si n égal 0 ou égal 1 renvoyer 1
     sinon renvoyer fib(n - 2) + fib(n - 1)
fin

Avec cette fonction, si tu demandes "fib(7)", le système cherchera à avoir fib(5) + fib(6). Il cherchera alors fib(5) en calculant fib(3) + fib(4); puis il cherchera fib(6) en calculant fib(4) une 2° fois + fib(5) là aussi une 2° fois etc et l'arbre récursif grossira de façon totalement exponentielle. En C, pour calculer fib(25) de cette façon, le programme me sort un résultat en 8 ou 9mn

Exemple en itératif

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
def fib(n)
debut
     u0=1
     u1=1
     si n égal 0 ou égal 1 renvoyer 1
 
     i=2
     u2=0
     tant que i <= n
     faire
          u2=u0 + u1           // Calcul de l'élément en cours
          u0=u1                  // Décalage pour l'itération suivante
          u1=u2                  // Idem
          i=i + 1
     fin faire
     renvoyer u2
fin

La fonction est plus complexe mais un appel à fib(7) génèrera une simple boucle de 5 itérations avec dans la boucle 2 aditions et 2 copies. Le calcul de fib(26) est instantané.

Conclusion => la récursivité c'est un beau concept mais faut toujours essayer de voir si on peut s'en passer...

[Jedai]

Conclusion => la récursivité c'est un beau concept mais faut toujours essayer de voir si on peut s'en passer...

Cette conclusion est typique de quelqu'un qui n'a jamais fait de programmation fonctionnelle, la récursion est terrible en C par exemple, mais dans d'autres langages elle est beaucoup plus exploitable. Il faut simplement réfléchir un peu différemment, tout en gardant l'oeil sur les cas où une récursion peu judicieuse peut entraîner un nombre exponentiel d'appels de fonction. Ecrire un fibonacci en récursif peut-être aussi rapide que la solution impérative, il suffit de changer légèrement la façon de faire :

Code Haskell :

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

1
2
3
fibonnacci n = snd (fib n)
    where fib 0 = (1,1)
          fib n = let (fn, fn') = fib (n-1) in (fn+fn', fn)

Cette fonction permet de calculer fibonnacci 20000 en moins d'un dixième de seconde en mode interprété et avec des "gros" entiers.

Evidemment, en Haskell, on ferait sans doute plutôt :

Code :

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

fibs = 1 : 1 : zipWith (+) fibs (tail fibs)

Ce qui donne une liste infinie de nombres représentant la suite de Fibonnacci (car qu'est-ce qu'une suite sinon une séquence infinie de nombres). Obtenir le 20000ème élément de cette suite est encore plus rapide que le code précédent, pratiquement instantanné.

--
Jedaï

[pseudocode]

Code Haskell :

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

1
2
3
fibonnacci n = snd (fib n)
    where fib 0 = (1,1)
          fib n = let (fn, fn') = fib (n-1) in (fn+fn', fn)

Cette fonction permet de calculer fibonnacci 20000 en moins d'un dixième de seconde en mode interprété et avec des "gros" entiers.

Dans ce cas la recursion sert a construire la liste de valeur = l'integralité de la suite de fibonnacci jusqu'a "n". C'est rapide meme avec un langage non fonctionnel.

Code java :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private BigInteger[] fib = null;
 
private void build(int n) {
	if (n==1 || n==2) {fib[n]=BigInteger.ONE;return;}
	if (fib[n-2]==null) build(n-2);
	if (fib[n-1]==null) build(n-1);
	fib[n]=fib[n-2].add(fib[n-1]);
}
 
private BigInteger fibonnacci(int n) {
	this.fib = new BigInteger[n+1];
	build(n);
	return fib[n];
}
// calcul fibonnacci(20000) en 300ms sur ma machine

Ce qui est long c'est de se servir de la recursion pour calculer "à chaque fois" un seul élément de la liste. Morale de la morale, utilisez la recursion pour "construire" la liste plutot que pour "evaluer" un de ses elements.

[Jedai]

D'un autre côté ton programme construit explicitement la liste, alors que le mien la construit implicitement, du coup ta solution est plus proche de ma deuxième solution (surtout considérant l'ordre réel du calcul, dû à l'évaluation paresseuse de Haskell).

Et bien sûr une solution récursive correcte est plus rapide qu'une incorrecte, que ce soit dans un langage fonctionnel ou dans un langage impératif, ce que je cherchais surtout à montrer c'est qu'en langage fonctionnel les solutions récursives étaient naturelles, bien plus qu'en impératif, et que rejeter en bloc la récursion comme mauvaise était complètement erroné, une idée héritée d'un temps où le C était le langage roi, où les compilateurs ne savaient pas optimiser les récursions terminales et où la pile était minuscule.

(Java n'est pas véritablement adapté à de la programmation récursive, ne serait-ce que parce qu'elle n'optimise pas la récursion terminale, du moins il en était ainsi la dernière fois que je m'étais posé la question).

Ce qui est long c'est de se servir de la recursion pour calculer "à chaque fois" un seul élément de la liste. Morale de la morale, utilisez la recursion pour "construire" la liste plutot que pour "evaluer" un de ses elements.

C'est un peu plus compliqué que ça, même si c'est une idée bonne à garder à l'esprit, tout dépend de la situation.

--
Jedaï

[pseudocode]

C'est sûr que rejeter en bloc la récursion est une très mauvaise idée. Ne serait-ce que pour le Quicksort.

Par contre, avec un langage imperatif, il vaut mieux reflechir a deux fois a son algo pour eviter les StackOverflow et les durées de traitement en million d'années...

Quand a Java, c'est clair qu'il ne vaut mieux pas l'utiliser pour la recursion.

du coup ta solution est plus proche de ma deuxième solution (surtout considérant l'ordre réel du calcul, dû à l'évaluation paresseuse de Haskell).

Promis, je me ferai une auto-formation Haskell des que j'ai le temps.