CSc 116 notes

Back     Next   Contents

9) Recursion

Recursion is a powerful mathematical technique, in which a function is defined in terms of itself. The standard example is the factorial function, the product of all integers up to its argument, written 3! = 3*2*1.

It is defined recursively as:

0! = 1
n! = n * (n-1)!   for n > 0

In recursion, there must always be at least one base case, for which no further recursion is required. Otherwise, the recursion would be infinite. A recursive function must test for this base case with an IF statement. Programmers who are used to loops often try to make this test part of a loop structure, this is incorrect. The recursive calls of factorial behave much like a loop, but the method is more general, and no FOR or WHILE statements are needed.

Implementation

A recursive function is implemented the same way as any other function that calls another function:

• The return address must be saved on the stack
• Space for local variables must be allocated on the stack, either directly, or indirectly, by using the s-registers, and saving their contents before use. (Fixed locations in the data segment cannot be used)
• And remember to test for the base case.

Historical note:

We didn't always know how to do this. In 1959, when the first version of FORTRAN was released, recursion was explicitly prohibited, because the original return address would be lost. In 1960 C. A. R. Hoare published the Quicksort algorithm, a very efficient recursive sorting method. His paper describing the implementation (in assembly language) mentions the use of "a unique data structure called a nest, which has the property that the last thing put in is the first thing taken out." Sound familiar? If the computer science world had been paying attention, we would be calling them nests instead of stacks today. Fortran didn't formally allow recursion until the Fortran 90 standard, 30 years later.

Factorial function

Here is a recursive implementation of factorial, first in C, then in assembly:

int factorial (int n){
    if (n < 2) return 1;
    return (n * factorial (n-1));  /* n! = n * (n-1)! */
}

factorial:
    bgtz  $a0, doit
        li   $v0, 1      # base case, 0! = 1
        jr   $ra
doit:
    sub  $sp,8           # stack frame 
    sw   $s0,($sp)       # will use for argument n   
    sw   $ra,4($sp)      #  return address

    move $s0, $a0        #  save argument
    sub  $a0, 1          #  n-1
    jal  factorial       #  v0 = (n-1)!
    mul  $v0,$s0,$v0     #     n*(n-1)!

    lw   $s0,($sp)       # restore registers from stack
    lw   $ra,4($sp) 
    add  $sp,8
    jr   $ra

Note that we used $s0 to save the value of n, after first saving its former value. And of course we save $ra. The result is that all the successive values of n are stacked up, and then used in the multiply instruction. Also, $a0 wasn't saved, and it will be 0 when we are all done.

Excescise: Modify this code so that $a0 is restored, by pushing and popping it. You shouldn't have to use $s0 or any more stack space than at present, but be careful where your pushes and pops go.

The towers of Hanoi

The standard non-trivial example of recursion is the "Towers of Hanoi" game. In this game there are 3 pegs, upon one of them is a stack of rings of different sizes, forming a tower. The challenge is to move the entire stack to another peg, following these rules:

1. Move only one ring at a time
2. A ring may never sit on top of a smaller ring

This takes a lot of time. According to legend, there is a game of 64 rings going on somewhere, with one ring being moved each second. When the new tower is complete, the world (universe) will come to an end. We have nothing to worry about, since adding a single ring to the game makes the time taken twice as long, plus one second, since the recursive procedure for moving a stack of rings from a source peg to a destination peg, using the third peg as a spare, is:

MoveStack(pegs: soruce, destination, spare; integer numberrings)
    MoveStack (source, spare, destination, numberrings -1)  #get all but bottom ring out of the way
    MoveRing  (source, destination)                         #move the bottom one
    MoveStack (spare, destination, source)                  # and pile the rest on top

This can be implemented by using some integer or pointer to identify the individual pegs, and has been in the programs

• hanoi.a, by John Waldron, in the textbook. Uses $s registers saved on the stack. Elegant printout.
• hanoi1.a, by Lin Jensen. Uses the stack frame to store the input pegs. Just writes out which moves to make.
• hanoi2.a same, but uses little "stacks of chars" to record ring locations, with simple printout.

Quicksort

Quicksort is a similar recursive algorithm, that is quite fast, in contrast to the towers. The idea is simply to break an array to be sorted into two arrays, and sort each of these. The tricky coding is in:

Partition:

Choose an array element at random, called the pivot element. Form two arrays:

• All elements < pivot
• All elements > pivot

Then just Quicksort each of these smaller arrays

The base case is an array of 1 element need not be sorted, as it cannot be out of order.

Finally, stick the smaller arrays and pivot together. Hoare defined Partition (for arrays) so that this is automatic.(No, I am not going to code it in assembly language in this millenium.)

Back    Next         Contents