CODEWITHSUNDEEP
recursionassemblyx86att
ech0
ech0

Reputation: 21

how does this recursive function works

I'm new to programming, and I'm starting to read a book about it to understand the fundamentals. I couldn't understand how the following assembly code works: it calculates the factorial of a number. I have added comments to the instructions that I can understand - clearly I'm missing something.

    .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`

Upvotes: 1

Views: 589

Answers (1)

Margaret Bloom
Margaret Bloom

Reputation: 44068

Don't comment acontextually, rather put the comments in context.

Don't write move the value 4 to %eax, instead find the meaning: move n to eax.
Don't keep track of the register values, keep track of the variables: else decrease the value by 1 is better as eax = n - 1

If you try commenting the program again you should arrive at something like the below.

.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

With these comments the function working is now unveiled - it is a pretty standard, non tail recursive, factorial implementation.

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

   return n * fact(n-1);
}

Questions about the execution flow, particularly what code is executed after the recursion closes, can be answered after a bit of use of a pencil and a rubber.
In the end you'll see that the important part to look for is the termination condition (termination case) - it is the input that won't span any more recursive call.
In this example is n = 1.

Another pillar necessary for a solid understanding of the function is how functions actually work - the fact that each invocation is an unique instance and that after a function return execution continues at the caller with the caller's state (the caller invocation is restored).
Thereby creating a (abstract) stack of saved/restored states.

The only peculiar aspect of that implementation is the instruction used to clean the stack of the function parameter.
If the sentence above throw you off, I advise to read about calling conventions.
Usually an addl $4, %esp is used, in the code a popl %ebx is used instead - while it makes sense in the factorial body since n is necessary again after the recursive call, its use is quite strange in the _start function.

Upvotes: 1

Related Questions