Caclul de factorielle

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Caclul de factorielle

kira974

Bonjour à tous,

Je débute ma formation en langage C et j'essaye de faire un programme me permettant de calculer la factorielle d'un nombre donnée, j'ai écrit le programme suivant :

Code :

#include <stdio.h>
 
 
int facto(int x) {
if (x==1) {
return 1;
}else{
facto(x-1)*x;
}
}
 
int main(){
 
int n;
printf("entrez un nombre : " );
scanf("%d",&n);
printf("facto(%d) = %d \n",n,facto(n));
system("pause" );
}

Or lorsque je rentre un chiffre différent de 1 la factorielle n'est pas calculée...pk et d'où vient mon erreur?

Merci pour vos réponses.

Message édité par Elmoricq le 04-12-2008 à 19:19:54

Publicité

toji

i am disappoint

ta fonction facto ne renvoit rien si x different de 1

kira974

dsl j'avais oublier de mettre le : return facto(x-1)*x;

Merci

Message édité par kira974 le 04-12-2008 à 18:57:50

Elmoricq

Modérateur

En vrac :
- main() est une fonction de type int mais n'a aucun return
- scanf() c'est mal, entre une chaîne de caractère pour le constater. Utilise fgets() + strtol()
- n'oublie pas de faire un petit test pour vérifier que le nombre entré est >=1. Sinon ton programme plantera sur une explosion de la pile (pas de condition d'arrêt à ta récursivité)
- et donc il manque le return à ta fonction si x != 1 (j'ai vu ta réponse, mais à tout hasard met à jour le code dans ton post pour qu'on voit où ça se situe, si tu as toujours le problème bien sûr)

jagstang

Pa Capona ಠ_ಠ

Tu arrives à me donner n! pour n=13 ?

quelques exemples aussi,

http://www.luschny.de/math/factorial/index.html

---------------
What if I were smiling and running into your arms? Would you see then what I see now?

Profil supprimé

La méthode avec for :

Code :

int facto(int x) {
    int result = 1;
 
    for(int i = x;i<1;i--) {
        result *= i;
    }
 
    return result;
}

est elle plus rapide que la méthode récursive ?
Merci

Joel F

Real men use unique_ptr

l'itératif est *en général* plus efficace que le récursif (modulo les trace caches ou les compilos sioux)

Message cité 1 fois

Profil supprimé

esox_ch

Joel F a écrit :

l'itératif est *en général* plus efficace que le récursif (modulo les trace caches ou les compilos sioux)

Mon prof d'image processing nous a dit exactement le contraire hier :heink:
Il nous a dit qu'en général le récursif est plus rapide mais que par contre t'as intérêt à avoir un ordio avec pas mal de RAM de bonne qualité sinon tu te manges la gueule..

Tu peux développer ta réponse du coup s'il te plait?

---------------
Si la vérité est découverte par quelqu'un d'autre,elle perd toujours un peu d'attrait

Joel F

Real men use unique_ptr

En gros, dans la plupart des langages fonctionels par contre, le récursif est en général comparable voir meilleurs que l'itératif -qui pose ne outre d'autre probleme.

Par contre, la récursivité dans les langages impératifs nécessite de sauvegarder le contexte d'appel et de potentiellement allouées enormement de variables locales sur la pile. Chaque coup te coute en outre les 4-5 cycles necessaires à effectuer le saut vers la fonction elle-même.

Sauf que, actuellement, pas mal de processeur on des caches de traces qui mémoisent les séquences d'instructions et les rechargent pas à chaque passage. Dans ce cas, la récursivité a un coup moindre car seul le cout sur la pile coute.
Fut aussi un temps ou certains front-end C tenter de dérécursifier les fonctions récursives à récursivité terminales, mais en je sais pas si ça a abouti.

Autre cas, la fonction qui calcule récursivement plusierus fois la meme valeur (genre fibonnacci et equivalent). Dans ce cas,l'algo récursif nécessite pour etre efficace d'etre réécrit sous forme d'algo de programmation dynamique qui va explicitement effectuer cette memoisation.

Message cité 1 fois

Publicité

esox_ch

Ok merci beaucoup

---------------
Si la vérité est découverte par quelqu'un d'autre,elle perd toujours un peu d'attrait

Gf4x3443

Killing perfection

Joel F a écrit :

Sauf que, actuellement, pas mal de processeur on des caches de traces qui mémoisent les séquences d'instructions et les rechargent pas à chaque passage. Dans ce cas, la récursivité a un coup moindre car seul le cout sur la pile coute.

C'est vraiment propre à l'x86, et son petit nombre de registres. Sur d'autres architectures, il y a des barillets, qui sollicitent beaucoup moins la pile que ne le ferait un programme sous x86.

Citation :

Fut aussi un temps ou certains front-end C tenter de dérécursifier les fonctions récursives à récursivité terminales, mais en je sais pas si ça a abouti.

Largement, les compilateurs aujourd'hui savent optimiser la plupart des tail-calls, exemple avec fact():

sans optimisation:

Code :

080486dc <fact>:
80486dc: 55 push %ebp
80486dd: 89 e5 mov %esp,%ebp
80486df: 83 ec 04 sub $0x4,%esp
80486e2: 83 7d 08 01 cmpl $0x1,0x8(%ebp)
80486e6: 7f 09 jg 80486f1 <fact+0x15>
80486e8: c7 45 fc 01 00 00 00 movl $0x1,0xfffffffc(%ebp)
80486ef: eb 19 jmp 804870a <fact+0x2e>
80486f1: 8b 45 08 mov 0x8(%ebp),%eax
80486f4: 48 dec %eax
80486f5: 83 ec 0c sub $0xc,%esp
80486f8: 50 push %eax
80486f9: e8 de ff ff ff call 80486dc <fact>
80486fe: 83 c4 10 add $0x10,%esp
8048701: 89 c2 mov %eax,%edx
8048703: 0f af 55 08 imul 0x8(%ebp),%edx
8048707: 89 55 fc mov %edx,0xfffffffc(%ebp)
804870a: 8b 45 fc mov 0xfffffffc(%ebp),%eax
804870d: c9 leave
804870e: c3 ret

avec:

Code :

080486dc <fact>:
80486dc: 55 push %ebp
80486dd: 89 e5 mov %esp,%ebp
80486df: 8b 55 08 mov 0x8(%ebp),%edx
80486e2: 83 fa 01 cmp $0x1,%edx
80486e5: 7e 18 jle 80486ff <fact+0x23>
80486e7: b8 01 00 00 00 mov $0x1,%eax
80486ec: eb 04 jmp 80486f2 <fact+0x16>
80486ee: 89 f6 mov %esi,%esi
80486f0: 89 ca mov %ecx,%edx
80486f2: 8d 4a ff lea 0xffffffff(%edx),%ecx
80486f5: 0f af c2 imul %edx,%eax
80486f8: 83 f9 01 cmp $0x1,%ecx
80486fb: 75 f3 jne 80486f0 <fact+0x14>
80486fd: c9 leave
80486fe: c3 ret
80486ff: b8 01 00 00 00 mov $0x1,%eax
8048704: c9 leave
8048705: c3 ret
8048706: 89 f6 mov %esi,%esi

Message cité 2 fois
Message édité par Gf4x3443 le 07-12-2008 à 16:32:57

---------------
Petit guide Kerberos pour l'administrateur pressé

Joel F

Real men use unique_ptr

Gf4x3443 a écrit :

C'est vraiment propre à l'x86, et son petit nombre de registres. Sur d'autres architectures, il y a des barillets, qui sollicitent beaucoup moins la pile que ne le ferait un programme sous x86.

Oui bien entendu.

Gf4x3443 a écrit :

Largement, les compilateurs aujourd'hui savent optimiser la plupart des tail-calls, exemple avec fact():

Ah bah voila maintenant je sais

MEI

|DarthPingoo(tm)|

Gf4x3443 a écrit :

C'est vraiment propre à l'x86, et son petit nombre de registres. Sur d'autres architectures, il y a des barillets, qui sollicitent beaucoup moins la pile que ne le ferait un programme sous x86.

Largement, les compilateurs aujourd'hui savent optimiser la plupart des tail-calls, exemple avec fact():

sans optimisation:

Code :

080486dc <fact>:
80486dc: 55 push %ebp
80486dd: 89 e5 mov %esp,%ebp
80486df: 83 ec 04 sub $0x4,%esp
80486e2: 83 7d 08 01 cmpl $0x1,0x8(%ebp)
80486e6: 7f 09 jg 80486f1 <fact+0x15>
80486e8: c7 45 fc 01 00 00 00 movl $0x1,0xfffffffc(%ebp)
80486ef: eb 19 jmp 804870a <fact+0x2e>
80486f1: 8b 45 08 mov 0x8(%ebp),%eax
80486f4: 48 dec %eax
80486f5: 83 ec 0c sub $0xc,%esp
80486f8: 50 push %eax
80486f9: e8 de ff ff ff call 80486dc <fact>
80486fe: 83 c4 10 add $0x10,%esp
8048701: 89 c2 mov %eax,%edx
8048703: 0f af 55 08 imul 0x8(%ebp),%edx
8048707: 89 55 fc mov %edx,0xfffffffc(%ebp)
804870a: 8b 45 fc mov 0xfffffffc(%ebp),%eax
804870d: c9 leave
804870e: c3 ret

avec:

Code :

080486dc <fact>:
80486dc: 55 push %ebp
80486dd: 89 e5 mov %esp,%ebp
80486df: 8b 55 08 mov 0x8(%ebp),%edx
80486e2: 83 fa 01 cmp $0x1,%edx
80486e5: 7e 18 jle 80486ff <fact+0x23>
80486e7: b8 01 00 00 00 mov $0x1,%eax
80486ec: eb 04 jmp 80486f2 <fact+0x16>
80486ee: 89 f6 mov %esi,%esi
80486f0: 89 ca mov %ecx,%edx
80486f2: 8d 4a ff lea 0xffffffff(%edx),%ecx
80486f5: 0f af c2 imul %edx,%eax
80486f8: 83 f9 01 cmp $0x1,%ecx
80486fb: 75 f3 jne 80486f0 <fact+0x14>
80486fd: c9 leave
80486fe: c3 ret
80486ff: b8 01 00 00 00 mov $0x1,%eax
8048704: c9 leave
8048705: c3 ret
8048706: 89 f6 mov %esi,%esi

J'dit p'tet une connerie, mais c'est pas pour les changement de contexte qu'on a invensté les registres virtuels ?

Ce qui fait qu'en realité le nombre de registre a un impact limité sur les perfs vu qu'on en a beaucoup plus en pratique. (meme si y'a des tables de translations et tout ça...)

Sinon THEORIQUEMENT, quelque soit le type de jeux d'instruction, une boucle for va BEAUCOUP plus vite qu'une fonction recursive.

Message cité 1 fois

---------------
| AMD Ryzen 7 7700X 8C/16T @ 4.5-5.4GHz - 64GB DDR5-6000 30-40-40 1T - AMD Radeon RX 7900 XTX 24GB @ 2680MHz/20Gbps |

Gf4x3443

Killing perfection

MEI a écrit :

J'dit p'tet une connerie, mais c'est pas pour les changement de contexte qu'on a invensté les registres virtuels ?

Principe des fenetres de registre: http://www.sics.se/~psm/sparcstack.html (entre autres).

Un changement de contexte est un cas particulier d'appel de fonction.

Citation :

Ce qui fait qu'en realité le nombre de registre a un impact limité sur les perfs vu qu'on en a beaucoup plus en pratique. (meme si y'a des tables de translations et tout ça...)

Euh si. Le nombre de registre, et la manière dont ils sont utilisés, a un impact sur la performance. Le design de la FPU de l'x86 en est le plus bel exemple foireux.

C'est un compromis: plus il y a de registres, et plus cela en fait à sauvegarder lors d'un changement de contexte (volontaire ou non). Quand ca n'est pas géré électroniquement, c'est couteux (les interruptions hard sur des DSP sont très lourdes pour cette raison).

---------------
Petit guide Kerberos pour l'administrateur pressé

FORUM HardWare.fr

Programmation

Caclul de factorielle

Sujets relatifs
[BASH] Factorielle - Script incorrect ?
Plus de sujets relatifs à : Caclul de factorielle

Page générée en 0.113 secondes