Discussion :

[.....1.....]

Bonjour à tous,

J'écris un binaire qui retourne un nombre de Fibonacci en fonction de l'indice qu'on lui passe. Pour cela, j'ai fait simple : j'utilise la récursivité. Voici le code :

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
int calcul_fibonacci(int fibonacci_number)
{
	if (fibonacci_number == 0)
	{
		return 0;
	}
	else if (fibonacci_number == 1 || fibonacci_number == 2)
	{
		return 1;
	}
	else
	{
		int resultat = (calcul_fibonacci(fibonacci_number - 1)) + (calcul_fibonacci(fibonacci_number - 2));
 
		return resultat;
	}
}

Donc ça fonctionne, mais c'est pas super optimal : pour des indices variant de 1 à 40, c'est presque instantané, pour un indice de 45, ça prend 13 seconde, mais pour un indice de 100, c'est effroyablement long.

Vous pensez que je peux corriger ça si je pars sur autre chose que sur une fonction récursive ?

D'avance merci'

[Xelland]

si tu restes en récursif :

supprimer les "else" : ils ne servent à rien

tu peux optimiser cette partie :

Code :

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

1
2
3
4
if (fibonacci_number == 1 || fibonacci_number == 2)
	{
		return 1;
	}

si c'est 2, alors tu fais 2 tests
alors qu'en 1 test, tu peux tester les 2 cas

tu gagneras un peu, mais pas tant que ça

[Bousk]

Il existe énormément d'écrits sur internet sur comment optimiser le calcul de la suite de fibonacci. Mais tu vas forcément te heurter à un mûr à un moment.
Le plus malin que je me souviens avoir lu utiliser un cache des 2 dernières valeurs qui passaient en paramètres.

[Sve@r]

Bonjour

Pour cela, j'ai fait simple : j'utilise la récursivité.

Hé oui. Le réflexe de base: je fais du récursif et c'est simple. Sauf que le récursif, c'est peut-être simple à écrire mais ce n'est pas gratuit. Chaque appel doit d'abord mettre l'appelant en "attente" puis calculer le résultat pour le lui renvoyer. Et quand c'est de la récursivité double (comme ici) ça devient exponentiel.

Donc ça fonctionne, mais c'est pas super optimal : pour des indices variant de 1 à 40, c'est presque instantané, pour un indice de 45, ça prend 13 seconde,

Et si pour 44 le temps est de (par exemple) 8 secondes, alors a mon avis, pour 46 ça devrait prendre 21 secondes, et 34 secondes pour 47...

mais pour un indice de 100, c'est effroyablement long.

Hé oui. Et tu t'es pas demandé ce qui se passe ? Pour 100 il faut calculer 99 et 98. Mais pour 99 il faut calculer 98 (une 2° fois) et 97. Pour 98 (donc calculé 2 fois) il faut 97 (déjà une fois) et 96. Pour 97 (qui en est maintenant à 3 fois) il faut 96 (déjà 2 fois) et 95. Pour 96 on en est à 5 fois. Je continue ???
Chose amusante: chaque indice est calculé un nombre de fois qui suit lui-même la suite de Fibonacci. 100 (1 fois), 99 (1 fois), 98 (2 fois), 97 (3 fois), 96 (5 fois), 95 (8 fois), 94 (13 fois) etc etc etc.

Vous pensez que je peux corriger ça si je pars sur autre chose que sur une fonction récursive ?

Fonction itérative. Un tableau unsigned long U[3]={1, 1} puis à chaque itération tu calcules U[2]=U[0]+U[1] puis tu copies U[1] dans U[0] et U[2] dans U[1]. A la fin de la boucle, le U[2] final est le nombre attendu. Tu pourras aller jusqu'à l'indice 50000 en 3 dixièmes de secondes.
Ca doit être d'ailleurs un réflexe de toujours tenter l'itératif en premier et de n'en venir au récursif que si vraiment on ne peut pas faire autrement. Ackerman par exemple, qu'on ne peut écrire en itératif qu'en utilisant les opérateurs de Knuth mais qui, eux, nécessitent la récursivité (autobaise quoi)...

[droggo]

Bonjour,

Pour Fibonacci, j'ai un calcul itératif, donc non récursif, et beaucoup plus rapide dès que n augmente.

le type uint_32 est tout simplement un unsigned int de 32 bits.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
uint_32 fiboIter(uint_32 n)
{
    uint_32 u = 1, v = 1, u0, v0;
    for (uint_32 i=2; i<=n; ++i)
    {
        u0 = u; v0 = v;
        u = u0 + v0;
        v = u0;
    }
    return u;
}

[Sve@r]

Pour Fibonacci, j'ai un calcul itératif, donc non récursif, et beaucoup plus rapide dès que n augmente.

Oui enfin tu ne fais que réécrire en C ce que j'ai dit. Et sinon v0 il sert à quoi concrètement ???

[.....1.....]

Who ! Quel succès

Merci à tous pour vos réponses.

@Xelland, tu penses que j'aurais dû faire 2 else if au lieu d'un seul ?

@Bousk ça marche, je farfouillerai.

@Sve@r Salut Oui c'est exactement ce que je me suis dit : la récursivité ça doit foutre la m****, cependant comme je ne suis pas un expert ni en C, ni en algorithmie, je suis parti là-dessus. Bien vu pour les temps de calcul, c'est bien ça : ça recalcule, donc ça accumule, donc on passe de 9 seconde à 13, puis à 21, etc...donc j'imagine bien qu'à 100 ça pique. Je vais partir sur ta suggestion alors, je posterai ça quand j'aurai fini.

@droggo merci pour le bout de code, ça m'évitera de réfléchir ah ah Par contre je suis d'accord avec Sve@r, je ne vois pas trop à quoi sert v0.

Bref, merci à vous et à bientôt avec un code optimal'

[droggo]

Bonjour,

Oui enfin tu ne fais que réécrire en C ce que j'ai dit. Et sinon v0 il sert à quoi concrètement ???

C'est une formule que j'avais établie il y a longtemps déjà, et manifestement j'avais oublié de la simplifier.

[Sve@r]

Who ! Quel succès

Bah, Fibonacci c'est un grand classique en prog. Surtout pour montrer en quoi la récursivité c'est pas toujours (et en réalité presque jamais) tiptop...

@Xelland, tu penses que j'aurais dû faire 2 else if au lieu d'un seul ?

Non. il dit juste que puisque la fonction quitte dans les deux premiers cas, pas beson d'écrire "else". Et surtout pas besoin de plusieurs tests préalables pour tester en réalité une alternative "je sors ou pas"

Code c :

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

1
2
3
4
5
6
unsigned long calcul_fibonacci(unsigned short fibonacci_number) {
 
	if (fibonacci_number <= 2)
		return fibonacci_number != 0 ?1 :0;
	return calcul_fibonacci(fibonacci_number - 1) + calcul_fibonacci(fibonacci_number - 2);
}

Voilà. Un seul test à chaque appel. Et le second test ne se fait que lors de quelques cas particuliers tandis que toi tu faisais 2 tests à chaque fois. A mon avis, pour 45 là où ça prenait 13 secondes ça devrait en prendre maintenant 12,99. Ceci dit, j'ai beau plaisanter, plus économique ne pourra jamais être pire que moins économique.

[.....1.....]

Re,

OK, merci pour le détail, j'avoue que je n'avais pas du tout compris ce qu'avait voulu dire Xelland.

Effectivement, cette petite expérience m'aura bien confirmé que le récursivité, c'est pas forcément génial

Merci à vous'

[droggo]

Bonjour,

Effectivement, cette petite expérience m'aura bien confirmé que le récursivité, c'est pas forcément génial

Et encore, ici ce n'est rien.

J'ai déjà vu des cours de programmation qui utilisent la récursivité pour calculer n! (factorielle n), ce qui est une pure idiotie.

[.....1.....]

J'ai déjà vu des cours de programmation qui utilisent la récursivité pour calculer n! (factorielle n), ce qui est une pure idiotie.

J'ai eu ça cette année - en C -. Mais de mémoire on nous a ensuite demandé de le faire sans utiliser la récursivité.

[Sve@r]

J'ai déjà vu des cours de programmation qui utilisent la récursivité pour calculer n! (factorielle n), ce qui est une pure idiotie.

Ce ne serait pas plutôt le contraire ? Utiliser la factorielle pour illustrer le concept de récursivité (ce qui est en général plus courant dans les cours de prog) ?

[droggo]

Bonjour,

Ce ne serait pas plutôt le contraire ? Utiliser la factorielle pour illustrer le concept de récursivité (ce qui est en général plus courant dans les cours de prog) ?

Désolé, mais la définition même de la factorielle conduit à l'utilisation d'une simple boucle for, et je n'y voit aucune trace de la nécessité de la récursivité.

[foetus]

je n'y voit aucune trace de la nécessité de la récursivité.

L'argument numéro 1 de la récursivité , c'est la simplicité d'écriture (souvent très proche de l'écriture mathématiques) size_t fac(size_t n) { return ((n > 1)? (n * fac(n - 1)): 1); }.

Pas de boucles, pas de piles (comme avec le tri rapide pour sauvegarder l'évolution des calculs), ...

[Sve@r]

Désolé, mais la définition même de la factorielle...

Ok. Donc en faisant abstraction (sans la renier) de la définition, utiliser une "façon de voir alternative" de la factorielle (après tout, 10! c'est aussi 10 * 9!) pour donc illustrer et apprendre ce qu'est la récursivité en prog...

[foetus]

Je viens de regarder et, avec la fonction factorielle, on peut expliquer la récursion terminale : Récursivité terminale(algorithme simple) (<- lien developpez.net)

size_t fac_aux(size_t n, size_t accu) { ((n > 1)? fac_aux((n - 1), (n * accu)): accu; } (et sûrement avec #define fac(n) fac_aux(n, 1))

[droggo]

Bonjour,

J'étais certain du résultat, mais j'ai quand même fait des tests, histoire de vous donner des chiffres.

Fibonacci récursif pour valeur = 49 : 47659 ms !!

Fibonacci Itératif pour valeur = 100 : < 1 ms

Je n'ai rien optimisé.

Amateurs de récursivité , à vos claviers.

[Stellar7]

Cela me ramène quelques (petites ?) années plus tôt, à la fac. En tant qu'étudiants, on avait un peu grommelé :
- passer la 2è année de Deug A/MP à comprendre et bien programmer la récursivité (pour voir ceux qui pouvaient changer de point de vue, de concept ?),
- dès la licence info, gros bourrinage travail pour apprendre à dé-récursiviser, car "le récursif, c'est le mal", à quelques exceptions près comme la récursivité terminale…

[Invité]

La récursivité permet de faire la même chose que les boucles et presque toujours aussi efficacement, si on ne la code pas n'importe comment. Par exemple, pour fibonacci :

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
#include <stdio.h>
#include <stdint.h>
 
uint64_t fib_aux(uint64_t n, uint64_t u, uint64_t v) {
    return n == 0 ? v : fib_aux(n-1, u+v, u);
}
 
uint64_t fib(uint64_t n) {
    return fib_aux(n, 1, 0);
}
 
int main() {
    printf("%llu\n", fib(93));
    return 0;
}

Et au passage, ça ne sert à rien d'aller au delà de 93 car les résultats ne tiennent plus sur 64 bits et sont donc faux.

Edit: j'oubliais le temps de calcul :

Code :

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

1
2
3
4
5
6
7
8
$ gcc -o fib fib.c 
 
$ time ./fib 
12200160415121876738
 
real	0m0,002s
user	0m0,002s
sys	0m0,001s