# Recursion in x86 Assembly

Using functions, it is also possible to implement recursion in x86 assembly. The idea of recursion is very similar to high-level languages; however, we need to still account for the typical calling conventions of x86 in our recursive calls.

Suppose we want to implement a factorial function, which calculates the factorial of a single parameter passed to it. To start, we are going to set up our function call the same as any other function. We will push the value we want to find the factorial of onto the stack, then call the factorial function. When it returns, we will move the result from *eax* to *ebx*, move 1 into *eax*, and interrupt the system.

Inside the factorial function is where things get a little more interesting. We start off by pushing *ebp *to the stack to set up our stack pointer and reference point. From here, we move *8(%ebp)* into *eax* to get our parameter off the stack. The end condition of our recursion is that the parameter we have is equal to 1, so we will check this first. We compare one to the current parameter and jump to the *end_factorial* method if they are equal. The *end_factorial *method completes all the typical cleanup of a function and returns to the previous *eip*.

If the parameter doesn't equal 1, we decrement it, then push it to the stack as a parameter, and call factorial again. The tricky part of assembly recursion is tracking where each *eip *is pointing. When we called the first time, *eip* is pointing to the next line in *_start*. The second time we call it, the *eip* will be pointing after this call, which will take care of pulling the new parameter off the stack, multiplying it by the current total in *eax*, and returning the result.

To understand how this recursion works, let's step through an example. Suppose that we wanted to find the factorial of 3. We push 3 onto the stack as a parameter, then call the factorial function. The factorial function sets up the *ebp *and *esp*, then moves the parameter into *eax*. At this point, our stack looks like below.

We compare the current parameter to 1, and since it isn't equal to 1, we proceed. We decrement *eax* from 3 to 2, then push it onto the stack, and recursively call the function. The function then proceeds to do the same setup as the first call, adding more data to our stack.

At this point, we once again compare the current parameter, 2, to the value 1. Since it isn't equal, we push it to the stack and complete a final recursive call.

At this point, when we check the parameter, it is equal to 1, which means we jump to end_factorial. When we get here, we move the *ebp *into *esp*, then pop *ebp *and return to the *eip *below it. This will place us directly at the line *movl 8(%ebp), %ebx* with a stack like below.

This move instruction will move 2 into *ebx*, since 2 is 8 memory units below the *ebp* value currently on the stack. Once this is done, we multiply this value by what is current in eax. Recall that when we got to 1, we loaded 1 into eax to compare it to our end condition. Due to this, 1 is still in eax, causing us to compute 1*2 = 2. So, currently, 2 is the value in *eax*.

Once this instruction is complete, we
progress to the next instruction which is in the end_factorial label. It is
important to note that just because an instruction is in a label, doesn't mean the
only way to access is to jump to it. Assembly will execute one instruction at a
time, moving down to the next instruction available until none are left. Due to
this, the next instruction to execute after the multiplication will be the
instructions found in the end_factorial label. This will do the same as before,
setup *ebp*, pop it from the stack, and
return the function. This returns back to *eip*,
which is the *movl 8(%ebp), %ebx *line,
with a stack like below.

From here, the parameter left on the stack is 3, so we move this to *ebx* and multiply by *eax* which currently has the value 2. This gives us a value of 6 in *eax*, which is the correct value for the factorial of 3. Once this is complete, we return once more, this time to the *eip* that points to _start. At this point, we increment *esp* to set it back to the correct location, move *eax *to *ebx *to preserve its value, then create a system interrupt. This ends the program, and the end value will be stored in *ebx* to be viewed through the command line.