Discussion :

[abd_bela]

Bonjour,

Je suis vraiment tres surpris par le résultat de la comparaison (temps d'execution ) entre une procédure itérative et récursive.
Alors que je pensais qu'une fonction récursive prend plus de temps à cause des appels successif de la fonction (sans parler des créations de variables locales à chaque appel!!)??? Le résultat est complètement l'inverse voici l'exemple :

// gcdIter.c

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
int main(int nb, char *arg[]){
 long  long  a=atoll(arg[1]);
 long  long  b=atoll(arg[2]);
 long  long  x, y,m=a; 
  if ( b < m) m=b; 
  while ( m != 0 ){ 
    x= a % m;  y= b % m;
    if (x == 0 && y == 0 )    break;
    m--;
  }
  printf("gcd of %ld %ld: %ld\n",a,b,m); 
  return 0;  
}

//gcdRecur.c

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
long long  gcd(long long  m, long long  n) {
    if ((m % n) == 0)  return n;
    else  return gcd(n, m % n);
 }
int main(int nb, char *arg[]){
  long long  a=atoll(arg[1]);
  long long  b=atoll(arg[2]);
  long long  m; 
  m=gcd(a,b); 
  printf("gcd of %ld %ld: %ld\n",a,b,m); 
  return 0;  
}

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
tmp$ gcc -o gi gcdIter.c 
tmp$ gcc -o gr gcdRecur.c 
tmp$ time ./gi 516323818 19996479344                    ------->   itératif
gcd of 516323818 19996479344: 2
 
real	0m14,192s
user	0m14,140s
sys	0m0,048s
tmp$ time ./gr 516323818 19996479344               ----------------->  récursif
gcd of 516323818 19996479344: 2
 
real	0m0,003s
user	0m0,000s
sys	0m0,003s

Bonne journée

[Sve@r]

Bonjour

Ce n'est pas évident de faire des tests de benchmark. Parce que linux peut avoir gardé en mémoire des traces des dernières actions (donc pas de swap) etc. Je ne dis pas que c'est le cas ici mais c'est un point à prendre en compte.
Par exemple moi pour faire ce test, j'aurais programmé deux shells qui attendent tous deux la présence d'un fichier X pour lancer le calcul, les aurais lancés tous deux en parallèle depuis deux fenêtres xterm puis créé le fichier depuis une 3°. Ainsi les calculs se seraient déroulés en même temps.

Autre chose: en récursivité il faut distinguer deux cas:

• la récursivité avec retour de calcul (exemple factorielle, fibonacci, pgcd)
• la récursivité qui se termine au dernier appel (appelée aussi "récursivité terminale"). Exemple affichage d'une chaine à l'envers (ou même à l'endroit), affichage d'un nombre X en base "b" (divisions successives), bref en fait toute fonction récursive appelée sans attendre son résultat (donc interdit d'écrire ...=fonction_recursive()). Là encore ce n'est pas le cas ici mais ça peut l'être ailleurs (donc j'en parle pour tes tests futurs)

Autre chose encore: quand on fait des tests, on essaye de rendre les codes testés le plus semblable possible (la seule différence portera par exemple sur la fonction de calcul). Ici tu as un algorithme itératif qui se déroule dans le main tandis que le récursif se déroule dans une fonction à part. Normalement tu aurais dû programmer deux gcd(), le premier itératif et le second résursif, tous deux lancés depuis leur main respectif. Alors ok l'itératif dans une fonction dédiée sera encore plus long que dans le main puisqu'on rajoutera le temps d'empilement/dépilement de la fonction mais là c'est pour l'impartialité des tests.

Maintenant (et là c'est le plus important), quand on compare un algorithme récursif vs algorithme itératif, on a au moins la décence de programmer le même algorithme !!!
La fonction récursive utilise l'algorithme d'Euclide (divisions successives) qui va aller très vite (si je pars par exemple de 1331 et 121, j'obtiens "11" en une opération. L'algorithme récursif, lui, utilise une méthode qui semble fonctionner mais à base de soustractions de b (ce m=b au début suivi de m-- que je ne m'explique pas). Et pour corser le tout, cet algorithme possède deux tests (le while (m !=0) suivi de if (x == 0 && y == 0 ) bien bien lourd avec son "and") !!!

Regarde ton algorithme tel que je l'ai réécrit avec un compteur d'affichage des opérations

Code c :

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
#include <stdio.h>
#include <stdlib.h>
 
long long gcd(long long a, long long b) {
	long long cpt=0;
	long long x, y,m=a;
	if ( b < m) m=b;
	while ( m != 0 ){
		cpt++;
		printf("cpt=%ld, a=%ld, b=%ld, m=%ld\n", cpt, a, b, m);
		x= a % m; y= b % m;
		if (x == 0 && y == 0 ) break;
		m--;
	}
	return m;
}
 
int main(int nb, char *arg[]){
	long long a=atoll(arg[1]);
	long long b=atoll(arg[2]);
	printf("gcd of %ld %ld: %ld\n",a,b,gcd(a, b));
	return 0; 
}

Et regarde le vrai algorithme d'Euclide (là aussi avec un compteur)

Code c :

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
#include <stdio.h>
#include <stdlib.h>
 
long long gcd(long long a, long long b) {
	long long m=a;
	long long cpt=0;
	while (b > 0) {
		cpt++;
		printf("cpt=%ld, a=%ld, b=%ld, m=%ld\n", cpt, a, b, m);
		m=a%b;
		a=b;
		b=m;
	}
	return a;
}
 
int main(int nb, char *arg[]){
	long long a=atoll(arg[1]);
	long long b=atoll(arg[2]);
	printf("gcd of %ld %ld: %ld\n",a,b,gcd(a, b));
	return 0; 
}

Et le rajout du compteur dans le récursif (que j'optimise encore un peu en supprimant le "else" inutile)...

Code c :

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
#include <stdio.h>
#include <stdlib.h>
 
long long gcd(long long m, long long n) {
	static long long cpt=0;
	cpt++;
	printf("cpt=%ld, a=%ld, b=%ld\n", cpt, m, n);
	if ((m % n) == 0) return n;
	return gcd(n, m % n);
}
 
int main(int nb, char *arg[]){
	long long a=atoll(arg[1]);
	long long b=atoll(arg[2]);
	printf("gcd of %ld %ld: %ld\n",a,b,gcd(a, b));
	return 0; 
}

Essaye-les avec par exemple 129236107 113365263 (le premier est 11 * 11 * 97 * 91 et le second est 11 * 11 * 89 * 87 et tu verras la différence dans le compteur de ton itératif par rapport au récursif ou de mon itératif. Ensuite supprime ce compteur et recommence tes tests. Et si tu veux bien charger le truc, il te faut alors choisir deux nombres consécutifs de la suite de Fibonacci comme par exemple le 49° et 50° qui sont 20365011074 et 32951280099 et qui produiront alors 51 itérations (et 20365011074 itérations avec ta version !!!)

[droggo]

Bonjour,

+1

Il est en effet très délicat de prendre le résultat de ce genre de test comme absolu

[Sve@r]

Ca y est, j'ai compris le premier algo itératif: c'est un algo brute force. On part de a et b et m égal au plus petit des deux et on tente de diviser a par m et b par m. Si ça marche ok sinon on décrémente m. Fatalement on finira par trouver un diviseur et ce sera le plus grand commun aux deux ; mais c'est l'algo le plus pourri qui puisse se programmer pour ce genre de calcul.
Mais qu'importe, puisque tu veux tester l'itératif et le récursif, voici les deux codes de cet algo
Itératif

Code c :

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
#include <stdio.h>
#include <stdlib.h>
 
long long gcd(long long a, long long b) {
	long long cpt=0;
	long long m=a < b ?a :b;
	while (1) {
		cpt++;
		printf("cpt=%ld, a=%ld, b=%ld, m=%ld\n", cpt, a, b, m);
		if (a%m == 0 && b%m == 0 ) return m;
		m--;
	}
}
 
int main(int nb, char *arg[]){
	long long a=atoll(arg[1]);
	long long b=atoll(arg[2]);
	printf("gcd of %ld %ld: %ld\n",a,b,gcd(a, b));
	return 0; 
}

Et le récursif

Code c :

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
#include <stdio.h>
#include <stdlib.h>
 
long long gcd(long long a, long long b, long long m) {
	static long long cpt=0;
	cpt++;
	printf("cpt=%ld, a=%ld, b=%ld, m=%ld\n", cpt, a, b, m);
	if (a%m == 0 && b%m == 0 ) return m;
	return gcd(a, b, m-1);
}
 
int main(int nb, char *arg[]){
	long long a=atoll(arg[1]);
	long long b=atoll(arg[2]);
	printf("gcd of %ld %ld: %ld\n",a,b,gcd(a, b, a < b? a :b));
	return 0; 
}

Le programme qui va les lancer (à appeler depuis deux fenêtres distinctes puis taper touch /tmp/x depuis une 3° pour qu'ils partent en même temps)

Code bash :

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

1
2
3
4
5
6
#!/bin/bash
until test -f "/tmp/x"; do
	true
done
echo "start $1"
time "./$1" "$2" "$3"

Et le résultat avec 97097 et 99500 (on peut pas aller beaucoup plus haut car la récursivité explose la pile)

Récursif
gcd of 97097 99500: 1
real 0m0,892s
user 0m0,043s
sys 0m0,136s

Itératif
gcd of 97097 99500: 1
real 0m0,805s
user 0m0,032s
sys 0m0,131s

[Bktero]

Et surtout : les deux programmes font un calcul (qui sera sans doute rapide) et un printf (qui sera sans doute lent). En gros, on mesure sans doute le temps des printf() et non le temps des calculs.

[Sve@r]

J'y ai pensé aussi. Mais quand on l'enlève, les deux programmes sont (malgré leur algo) trop rapides (0.003s pour le récursif et 0.002s pour l'itératif). Même si l'itératif reste plus rapide, les écarts ne sont plus assez significatifs pour pouvoir en discuter.
Et si j'augmente les nombres à chercher, le récursif (qui fera autant d'appels que la valeur du plus petit des deux nombres) explose en vol.

Je me suis donc dit que puisque les printf sont tous deux présents au même endroit, cela chargeait les deux programmes de façon égale ce qui annulait cette charge au résultat (la différence de temps étant donc due à la différence récursif/itératif et non due aux printf)...

[abd_bela]

Merci pour tous vos commentaires et suggestions.
Je vais reprendre et modifier mes programmes et tester les votres.
bonne journée.

[abd_bela]

Rebonjour,
J ai repris le pgcd itératif et récursif (avec le meme algorithme pardi !!!!), pratiquement pas de différence de temps, mais pour fibonacci la différence est tres importante, une idée pourquoi cette différence. Ci-joint les tests. Il est plus interressant d'utiliser la fonction time .
Les programmes sont mis dans les meme conditions, un meme printf en fin de programme.

Il n'est pas nécessaire de faire l'execution en meme temps, la fonction time donne suffisamment d'information.

Merci pour la discussion.

************PGCD 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
18
19
20
21
22
23
24
#include <stdio.h>
#include <stdlib.h>
#define ull unsigned long long 
ull gcd(ull a, ull b) {
	ull m=a;
	while (b > 0) {
		m=a%b;  a=b; 		b=m;
	}
	return a;
}
int main(int nb, char *arg[]){
	ull r,  a=atoll(arg[1]);
	ull b=atoll(arg[2]);
	r=gcd(a, b);
	printf("\nIterative: gcd of %ld %ld: %ld\n",a,b,r);
	return 0; 
}
/**
 *  time ./gIter   5957444661174968386 4376692037216111008
 * Iterative: gcd of 5957444661174968386 4376692037216111008: 2
 * real 0m0,003s
 * user 0m0,002s
 * sys  0m0,000s
 * */

*****************PGCD Récursif *************

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
 
#include <stdio.h>
#include <stdlib.h>
#define ull unsigned long long 
ull gcd(ull  m, ull  n) {
	if ((m % n) == 0)		return n;
	return gcd(n, m % n);
}
 
int main(int nb, char *arg[]){
	ull  r, a=atoll(arg[1]);
	ull  b=atoll(arg[2]);
	r=gcd(a, b);
	printf("\nRecursif: gcd of %ld %ld: %ld\n",a,b,r);
	return 0; 
}
/**
 * time ./gRec   5957444661174968386 4376692037216111008
 * Recursif: gcd of 5957444661174968386 4376692037216111008: 2
 * real 0m0,003s
 * user 0m0,002s
 * sys  0m0,000s
**/

********************************************
*************** Fibo Recursive *************

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
#include <stdio.h>
#include <stdlib.h>
long long recurfib(long long n){
   if (n == 1 || n == 2) 	 return 1;
   return recurfib(n-1) + recurfib(n-2);
}
int main(int nb, char *arg[]){
	long long r,  a=atoll(arg[1]);
	r=recurfib(a);
	printf("\nFibo Recursive: n=%ld: fibo : %ld \n",a,r);
	return 0; 
}
/**  
 * time ./frec 44
 * Fibo Recursive: n=44: fibo : 701408733 
 * real 0m6,220s
 * user 0m6,211s
 * sys  0m0,001s
 * **/

****************Fibo Iterative ***************

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
 
#include <stdio.h>
#include <stdlib.h>
#define ull unsigned long long 
ull  iterfib(ull n){
   ull a=0, tmp, i,  b =  1;
   for ( i=0; i < n; i++){
      tmp=b; b +=a; a=tmp;
   }
   return a;
}
int main(int nb, char *arg[]){
	ull r,  a=atoll(arg[1]);
	r=iterfib(a);
	printf("\nFibo Iterative: n=%lu: fibo : %lu \n",a,r);
	return 0; 
}
/**
 * time ./fiter  44
 * Fibo Iterarive: n=44: fibo : 701408733 
 * real 0m0,002s
 * user 0m0,002s
 * sys  0m0,001s
**/

Merci pour votre aide

[Sve@r]

mais pour fibonacci la différence est tres importante, une idée pourquoi cette différence

Bien sûr !!!
La Fibonacci illustre le concept de "récursivité double" où une fonction s'appelle elle-même plusieurs fois (le "double" ne s'arrétant alors pas forcément à "2 fois").
Prenons exemple de recurfib(30). Ta fonction va alors demander recurfib(29) + recurfib(28). Pour recurfib(29) elle va demander recurfib(28) (déjà demandé) + recurfib(27). Pour récurfib(28) (demandé 2 fois) elle va demander recurfib(27) + recurfib(26). Et etc etc.
Et (chose amusante), le nombre de demandes est exactement égal à la suite de Fibonacci. recurfib(30) sera demandé 1 fois tout comme recurfib(29). recurfib(28) sera demandé 2 fois, recurfib(27) demandé 3 fois, recurfib(26) demandé 5 fois, recurfib(25) demandé 8 fois, recurfib(24) demandé 13 fois et etc jusqu'à recurfib(1) qui sera demandé 832040 fois.

Fibonacci c'est exactement l'exemple qu'on utilise pour montrer que la récursivité est souvent une "fausse" bonne idée et qu'il vaut mieux privilégier l'itératif à chaque fois qu'on le peut. Malheureusement on ne peut pas tout le temps (Ackermann par exemple).