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