Comparaison fonctions itérative et récursive
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:
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:
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:
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
Comparaison fibonacci iterative et recursive
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:
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:
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:
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:
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
