Recursive Functions | Programming from the Ground Up

The next program will stretch your brains even more. The program will compute the factorial of a number. A factorial is the product of a number and all the numbers between it and one. For example, the factorial of 7 is 7*6*5*4*3*2*1, and the factorial of 4 is 4*3*2*1. Now, one thing you might notice is that the factorial of a number is the same as the product of a number and the factorial just below it. For example, the factorial of 4 is 4 times the factorial of 3. The factorial of 3 is 3 times the factorial of 2. 2 is 2 times the factorial of 1. The factorial of 1 is 1. This type of definition is called a recursive definition. That means, the definition of the factorial function includes the factorial function itself. However, since all functions need to end, a recursive definition must include a base case. The base case is the point where recursion will stop. Without a base case, the function would go on forever calling itself until it eventually ran out of stack space. In the case of the factorial, the base case is the number 1. When we hit the number 1, we don't run the factorial again, we just say that the factorial of 1 is 1. So, let's run through what we want the code to look like for our factorial function:

Examine the number
Is the number 1?
If so, the answer is one
Otherwise, the answer is the number times the factorial of the number minus one

This would be problematic if we didn't have local variables. In other programs, storing values in global variables worked fine. However, global variables only provide one copy of each variable. In this program, we will have multiple copies of the function running at the same time, all of them needing their own copies of the data!^[6] Since local variables exist on the stack frame, and each function call gets its own stack frame, we are okay.

Let's look at the code to see how this works:

  #PURPOSE - Given a number, this program computes the  #          factorial.  For example, the factorial of  #          3 is 3 * 2 * 1, or 6.  The factorial of  #          4 is 4 * 3 * 2 * 1, or 24, and so on.  #  #This program shows how to call a function recursively.  .section .data  #This program has no global data  .section .text  .globl _start  .globl factorial #this is unneeded unless we want to share                   #this function among other programs _start:  pushl $4         #The factorial takes one argument - the                   #number we want a factorial of.  So, it                   #gets pushed  call  factorial  #run the factorial function  addl  $4, %esp   #Scrubs the parameter that was pushed on                   #the stack  movl  %eax, %ebx #factorial returns the answer in %eax, but                   #we want it in %ebx to send it as our exit                   #status  movl  $1, %eax   #call the kernel's exit function  int   $0x80  #This is the actual function definition  .type factorial,@function factorial:  pushl %ebp       #standard function stuff - we have to                   #restore %ebp to its prior state before                   #returning, so we have to push it  movl  %esp, %ebp #This is because we don't want to modify                   #the stack pointer, so we use %ebp.  movl  8(%ebp), %eax #This moves the first argument to %eax                   #4(%ebp) holds the return address, and                   #8(%ebp) holds the first parameter  cmpl  $1, %eax      #If the number is 1, that is our base                      #case, and we simply return (1 is                      #already in %eax as the return value)  je end_factorial  decl  %eax          #otherwise, decrease the value  pushl %eax          #push it for our call to factorial  call  factorial     #call factorial  movl  8(%ebp), %ebx #%eax has the return value, so we                      #reload our parameter into %ebx  imull %ebx, %eax    #multiply that by the result of the                      #last call to factorial (in %eax)                      #the answer is stored in %eax, which                      #is good since that's where return                      #values go. end_factorial:  movl  %ebp, %esp    #standard function return stuff - we  popl  %ebp          #have to restore %ebp and %esp to where                      #they were before the function started  ret                 #return from the function (this pops the                      #return value, too)

Assemble, link, and run it with these commands:

 as factorial.s -o factorial.o ld factorial.o -o factorial ./factorial echo $?

This should give you the value 24. 24 is the factorial of 4, you can test it out yourself with a calculator: 4 * 3 * 2 * 1 = 24.

I'm guessing you didn't understand the whole code listing. Let's go through it a line at a time to see what is happening.

 _start:  pushl $4  call factorial

Okay, this program is intended to compute the factorial of the number 4. When programming functions, you are supposed to put the parameters of the function on the top of the stack right before you call it. Remember, a function's parameters are the data that you want the function to work with. In this case, the factorial function takes 1 parameter - the number you want the factorial of.

The pushl instruction puts the given value at the top of the stack. The call instruction then makes the function call.

Next we have these lines:

          addl  $4, %esp          movl  %eax, %ebx          movl  $1, %eax          int   $0x80

This takes place after factorial has finished and computed the factorial of 4 for us. Now we have to clean up the stack. The addl instruction moves the stack pointer back to where it was before we pushed the $4 onto the stack. You should always clean up your stack parameters after a function call returns.

The next instruction moves %eax to %ebx. What's in %eax? It is factorial's return value. In our case, it is the value of the factorial function. With 4 as our parameter, 24 should be our return value. Remember, return values are always stored in %eax. We want to return this value as the status code to the operating system. However, Linux requires that the program's exit status be stored in %ebx, not %eax, so we have to move it. Then we do the standard exit system call.

The nice thing about function calls is that:

Other programmers don't have to know anything about them except its arguments to use them.
They provide standardized building blocks from which you can form a program.
They can be called multiple times and from multiple locations and they always know how to get back to where they were since call pushes the return address onto the stack.

These are the main advantages of functions. Larger programs also use functions to break down complex pieces of code into smaller, simpler ones. In fact, almost all of programming is writing and calling functions.

Let's now take a look at how the factorial function itself is implemented.

Before the function starts, we have this directive:

  .type factorial,@function factorial:

The .type directive tells the linker that factorial is a function. This isn't really needed unless we were using factorial in other programs. We have included it for completeness. The line that says factorial: gives the symbol factorial the storage location of the next instruction. That's how call knew where to go when we said call factorial.

The first real instructions of the function are:

  pushl %ebp  movl  %esp, %ebp

As shown in the previous program, this creates the stack frame for this function. These two lines will be the way you should start every function.

The next instruction is this:

  movl  8(%ebp), %eax

This uses base pointer addressing to move the first parameter of the function into %eax. Remember, (%ebp) has the old %ebp, 4 (%ebp) has the return address, and 8 (%ebp) is the location of the first parameter to the function. If you think back, this will be the value 4 on the first call, since that was what we pushed on the stack before calling the function the first time (with pushl $4). As this function calls itself, it will have other values, too.

Next, we check to see if we've hit our base case (a parameter of 1). If so, we jump to the instruction at the label end_factorial, where it will be returned. It's already in %eax which we mentioned earlier is where you put return values. That is accomplished by these lines:

  cmpl $1, %eax  je end_factorial

If it's not our base case, what did we say we would do? We would call the factorial function again with our parameter minus one. So, first we decrease %eax by one:

  decl %eax

decl stands for decrement. It subtracts 1 from the given register or memory location (%eax in our case). incl is the inverse - it adds 1. After decrementing %eax we push it onto the stack since it's going to be the parameter of the next function call. And then we call factorial again!

  pushl %eax  call factorial

Okay, now we've called factorial. One thing to remember is that after a function call, we can never know what the registers are (except %esp and %ebp). So even though we had the value we were called with in %eax, it's not there any more. Therefore, we need pull it off the stack from the same place we got it the first time (at 8 (%ebp)). So, we do this:

  movl 8(%ebp), %ebx

Now, we want to multiply that number with the result of the factorial function. If you remember our previous discussion, the result of functions are left in %eax. So, we need to multiply %ebx with %eax. This is done with this instruction:

  imull %ebx, %eax

This also stores the result in %eax, which is exactly where we want the return value for the function to be! Since the return value is in place we just need to leave the function. If you remember, at the start of the function we pushed %ebp, and moved %esp into %ebp to create the current stack frame. Now we reverse the operation to destroy the current stack frame and reactivate the last one:

 end_factorial:  movl %ebp, %esp  popl %ebp

Now we're already to return, so we issue the following command

ret

This pops the top value off of the stack, and then jumps to it. If you remember our discussion about call, we said that call first pushed the address of the next instruction onto the stack before it jumped to the beginning of the function. So, here we pop it back off so we can return there. The function is done, and we have our answer!

Like our previous program, you should look over the program again, and make sure you know what everything does. Look back through this section and the previous sections for the explanation of anything you don't understand. Then, take a piece of paper, and go through the program step-by-step, keeping track of what the values of the registers are at each step, and what values are on the stack. Doing this should deepen your understanding of what is going on.

^[6]By "running at the same time" I am talking about the fact that one will not have finished before a new one is activated. I am not implying that their instructions are running at the same time.