Tutorials on Advanced Math and Computer Science Concepts

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.