Pile d'exécution pour la fonction factorielle récursive

Version imprimable

01/12/2009, 14h47
HASALGO

Pile d'exécution pour la fonction factorielle récursive

Bonjour,
svp, je veux savoir le remplissage pas à pas de la pile lors de l'exécution de la fonction récursive de calcul du factoriel(n), pour par exemple n = 4
Merci
01/12/2009, 15h31
M.Dlb

Pour savoir ça, tu prends un papier et un crayon et tu traces "à la main".
11/12/2009, 13h05
HASALGO

C'est ça ce que je veux savoir! l'execution à la main : qu'est-ce qu'on range dans la pile? donnez moi un exemple svp!
merci

pfff

Code:

1
2
3
4
5
6
7
8
 
function Fact(N: LongInt): LongInt;
begin
  if N <= 1 then
    result := 1
  else
    result := N * Fact(N-1);
end;

en assembleur :

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
25
26
27
28
29
30
 
Fact(10);
0040B170 mov eax,$0000000a // 10
0040B175 call Fact 
 
 
function Fact(N: LongInt): LongInt;
begin
  $0040AD64 push ebx
  $0040AD65 mov ebx,eax
 
  if N <= 1 then
    $0040AD67 cmp ebx,$01 
    $0040AD6A jnle $0040ad73
 
    result := 1
    $0040AD6C mov eax,$00000001 
    $0040AD71 pop ebx
    $0040AD72 ret 
 
  else
    result := N * Fact(N-1);
    $0040AD73 mov eax,ebx 
    $0040AD75 dec eax
    $0040AD76 call Fact
    $0040AD7B imul ebx
 
end;
$0040AD7D pop ebx
$0040AD7E ret

Code:

1
2
3
4
5
6
7
8
 
function Fact(N: LongInt): extended;
begin
  if N <= 1 then
    result := 1
  else
    result := N * Fact(N-1);
end;

qui génére l'assembleur suivant :

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Fact(10);
  $0040B1B8 mov eax,$0000000a
  $0040B1BD call Fact
  $0040B1C2 fstp st(0)
 
 
functon Fact(N: LongInt): extended;
begin
$0040AD64 push ebx
$0040AD65 add esp,-$10
$0040AD68 mov ebx,eax
 
  if N <= 1 then
  $0040AD6A cmp ebx,$01 
  $0040AD6D jnle $0040ad85
 
    result := 1
    $0040AD6F xor eax,eax
    $0040AD71 mov [esp],eax
    $0040AD74 mov [esp+$04],$80000000
    $0040AD7C mov word ptr [esp+$08],$3fff
    $0040AD83 jmp $0040ad9b
 
  else
    result := N * Fact(N-1);
    $0040AD85 mov eax,ebx
    $0040AD87 dec eax
    $0040AD88 call Fact
    $0040AD8D mov [esp+$0c],ebx
    $0040AD91 fild dword ptr [esp+$0c]
    $0040AD95 fmulp st(1)
    $0040AD97 fstp tbyte ptr [esp]
    $0040AD9A wait 
end;
$0040AD9B fld tbyte ptr [esp]
$0040AD9E add esp,$10
$0040ADA1 pop ebx
$0040ADA2 ret

bonne analyse.

24/12/2009, 17h35
HASALGO

merci pour votre aide mais je comprend pas en assembleur, si vous pouvez m'expliquer autrement par exemple dessinez moi la pile d'execution de cet exemple à savoir que je veux une solution simple, clair et facile à comprendre comportant le minimum nécessaire pour comprendre comment s'execute un module récursif.
merci pour votre aide
25/12/2009, 11h21
Alcatîz

Bonjour,

Lors de l'appel d'une telle fonction, toute simple, le paramètre N est tout d'abord déposé sur la pile, puis l'adresse de retour (pour pouvoir poursuivre l'exécution du programme lorsque la fonction s'achève). La récursion entraîne peu de consommation de pile.

Mais si une fonction reçoit des paramètres de type complexe par valeur, une copie temporaire en est faite sur la pile. S'il y a des variables locales, elles sont toutes réservées dans la pile. Une utilisation récursive d'une telle fonction peut vite faire exploser la pile.

Poste-nous le code exact de ta fonction et nous t'aiderons à dresser un plan de la pile lors de son exécution. ;)
27/12/2009, 00h29
HASALGO
bonsoir,
voilà mon exemple :
Soit la procédure suivante:
Code:

1 2 3 4 5 6 7 8 procedure tester (n:integer); begin if n>0 then begin tester (n div 2); write(n mod 2); end; end;
Qu’affiche cette procédure dans chacun des cas suivants: N=13, N= -5, N=0 et N = 19. expliquez le déroulement de l’exécution de la procédure.
27/12/2009, 12h57
droggo

Goe,

Citation:

Envoyé par HASALGO

Qu’affiche cette procédure dans chacun des cas suivants: N=13, N= -5, N=0 et N = 19. expliquez le déroulement de l’exécution de la procédure.

En clair, c'est un exercice scolaire.

Exécute ton programme, regarde l'affichage, et éventuellement note-le.

PUIS, papier + crayon, et tu exécutes manuellement ligne par ligne, en notant bien toutes les valeurs des variables, etc.
Ça devrait te faire comprendre.