wie funktioniert diese rekursive Funktion

Question

Ich bin neu in der Programmierung, und ich fange an, ein Buch darüber zu lesen, um die Grundlagen zu verstehen. Ich konnte nicht verstehen, wie der folgende Assembler-Code funktioniert: Er berechnet den Faktor einer Zahl. Ich habe Kommentare zu den Anweisungen hinzugefügt, die ich verstehen kann - klar, dass mir etwas fehlt.

.section .data 
    .section .text 
    .globl _start 
    .globl factorial 

_start: 

    pushl $4    
    call factorial   
    popl %ebx    
    movl %eax, %ebx   
    movl $1, %eax   
    int $0x80 

factorial: 

    pushl %ebp    # push the base pointer 
    movl %esp, %ebp   # copy the stack pointer to the base pointer 
    movl 8(%ebp), %eax  # move the value 4 to %eax 
    cmpl $1, %eax   # compare it to 1 
    je end_factorial  # jump to end_factorial if it's equal 
    decl %eax    # else decrease the value by 1 
    pushl %eax    # push the decreased value in the stack 
    call factorial   # this means that it should start again (?) 

    popl %ebx    # that's the part that i don't understand 
    incl %ebx    # when are these lines excuted? since it 
    imul %ebx, %eax   # keeps starting from the top, until the value 
          # of %eax is 1 then, it jumps to end_factorial 

end_factorial: 

    movl %ebp, %esp 
    popl %ebp 
    ret` 

Answer 1

Kommentieren Sie nicht akontextuell, sondern setzen Sie die Kommentare in Kontext.

Schreiben nicht den Wert 4 bis% eax, stattdessen die Bedeutung finden bewegen: n bewegt eax.
Bewahren Sie keine Spur der Registerwerte, verfolgen die Variablen: sonst von 1 den Wert verringern ist besser als EAX = n - 1

Wenn Sie das Programm erneut versuchen zu kommentieren Sie ankommen sollten auf etwas wie das unten.

.section .data 
.section .text 

.globl _start     
.globl factorial 

_start: 

    pushl $4    
    call factorial   # eax = 4! 
    popl %ebx    # Remove the parameter from the stack  

    movl %eax, %ebx 
    movl $1, %eax   
    int $0x80    # sys_exit(4!) 

factorial: 

    pushl %ebp 
    movl %esp, %ebp   # Prolog 

    movl 8(%ebp), %eax  # eax = n 

    cmpl $1, %eax   # n == 1? 
    je end_factorial  # If yes, since 1! = 1, just return 

    decl %eax    # eax = n - 1 

    pushl %eax    
    call factorial   # eax = (n - 1)! 

    popl %ebx    # ebx = (n - 1) 
    incl %ebx    # ebx = n 
    imul %ebx, %eax   # eax = n * (n - 1)! = n! 

end_factorial: 

    movl %ebp, %esp   # Prolog 
    popl %ebp 
    ret 

Mit diesen Kommentaren die Funktion arbeitet nun enthüllt wird - es ist ein ziemlich Standard, nicht Schwanz rekursiv, faktorielles Implementierung.

int fact(int n) 
{ 
    if (n == 1) 
     return 1; 

    return n * fact(n-1); 
} 

Fragen zum Ausführungsablauf, vor allem, was den Code ausgeführt wird, nachdem die Rekursion schließt, können nach einem bisschen Verwendung von Bleistift und Gummi beantwortet werden.
Am Ende werden Sie sehen, dass der wichtige Teil für die Suche ist die Terminierungsbedingung (Terminierungsfall) - es ist die Eingabe, die nicht mehr rekursiven Aufruf umfassen wird.
In diesem Beispiel ist n = 1.

Eine weitere Säule, die für ein solides Verständnis der Funktion ist, wie Funktionen tatsächlich funktionieren - die Tatsache, dass jeder Aufruf eine eindeutige Instanz ist und dass nach einer Funktion Rückkehr Ausführung fortgesetzt an dem Anrufer mit den staatlichen Anrufern (der Anrufer Aufruf ist wiederhergestellt).
Dadurch wird eine (abstrakte) Stapel der gespeicherten/wiederhergestellten Staaten erstellt.

Der einzige merkwürdige Aspekt dieser Implementierung ist der Befehl, der zum Löschen des Stapels des Funktionsparameters verwendet wird.
Wenn der obige Satz dich abstößt, empfehle ich, über calling conventions zu lesen.
Normalerweise wird eine addl $4, %esp verwendet wird, in dem Code ein popl %ebx stattdessen verwendet wird - während es sinnvoll, im factorial Körper da n macht notwendig ist, wieder nach dem rekursiven Aufruf, seine Verwendung in der _start Funktion ziemlich seltsam.