8.3: Recursion

In computer science, recursion is a mechanism to a way to divide a problem up into successively smaller instances of the same problem until some stopping condition (or base case) is reached. The individual solutions to all of the smaller problems are then gathered together and an overall solution to the problem is obtained. This technique is very powerful for specifying unbounded problems which contain some common description of all parts of the problem. This is common with searching problems, such as trying to find all web pages which are reachable from a given web page. Since the number of connections to any page is unbounded, it is not possible to design a program using looping structures to find all of the pages, and recursion is a natural solution to this problem.

Unfortunately the types of problems that easily lend themselves to recursive solutions are more complex than can be covered in an introductory programming text such as this. Thus the example problems which are presented are more easily solved using other means like iteration. Many programmers studying recursion are left wondering why bother with the recursion, and recursion is seen as hard and not very useful.

Having said about recursion, this chapter will also present recursion using simple problems that can more easily be solved using iteration. Most of the problems at the end of the chapter will also fall into this category. It is difficult to present a true use of recursion without clouding the details of how recursion is implemented, or implementing more complex data structures that would require a complete and separate treatment to explain.

8.3.1 Recursive multiply in a HLL

To implement recursion, both the current state of the solution as well as the path that has lead to this state must be maintained. The current state allows the problem to be further subdivided as the recursion proceeds in a forward manner towards the base case. The path to the current state allows the results to be gathered together back together to achieve the results. This is a perfect situation for a stack.

An example is a recursive definition of a multiply operation. Multiplication can be defined as adding the multiplier (m) to itself the number of times in the multiplicand (n) times. Thus a recursive definition of multiplication is the following:

M(m,n) = m (when n = 1)
         else M(m, n-1)

This is implemented in pseudo code below.

subprogram global main() 
{
    register int multiplicand
    register int multiplier
    register int answer
    m = prompt("Enter the multiplicand") 
    n = prompt("Enter the multiplier") answer = Multiply(m, n)
    print("The answer is: " + answer)
}
subprogram int multiply(int m, int n)
{
    if (n == 1)
        return m;
    return m + multiply(m,n-1)
}            

The following MIPS assembly language program implements the above pseudo code program. Note that at the start of each call to multiply the $ra is stored. In all cases but the first call to the subprogram the $ra will contain the same address. The stack records storing the $ra are really just a way to count how far into the stack the program has gone, so it can return the correct number of times.

There is one other piece of data that has been stored on the program stack and that is the value of $a1. As the programmer of this subprogram I know that $a1 will not be changed in subsequent calls to multiply. However the agreement to return register values unchanged only applies to the save registers ($s0..$s8). It is perfectly valid for subprograms to change any other register values. So there is no guarantee that the value in $a0 will not be changed once any subprogram is called. Prudence dictates that therefore it be saved, and the only save place to save it is on the stack.

Program 8-3: Recursive multiplication

.text
.globl main
main:
    # register conventions
    #  $s0 - m
    #  $s1 - n
    #  $s2 - answer
    
    la $a0, prompt1        # Get the multiplicand
    jal PromptInt
    move $s0, $v0
    
    la $a0, prompt2        # Get the multiplier
    jal PromptInt
    move $s1, $v0
    
    move $a0, $s0
    move $a1, $s1
    
    jal Multiply           # Do multiplication
    move $s2, $v0
    
    la $a0, result         #Print the answer
    move $a1, $s2
    jal PrintInt
    
    jal Exit

Multiply:
    addi $sp, $sp -8.      # push the stack
    sw $a0, 4($sp)         #save $a0
    sw $ra, 0($sp)         # Save the $ra
    
    seq $t0, $a1, $zero    # if (n == 0) return
    addi, $v0, $zero, 0    # set return value
    bnez $t0, Return
    
    addi $a1, $a1, -1      # setn=n-1
    jal Multiply           # recurse
    lw $a0, 4($sp)         # retrieve m
    add $v0, $a0, $v0      # return m+multiply(m, n-1)
    
    Return:
    lw $ra, 0($sp)         #pop the stack
    addi $sp, $sp, 8
    jr $ra

.data
prompt1: .asciiz "Enter the multiplicand: "
prompt2: .asciiz "Enter the multiplier: "
result:  .ascii "The answer is: "
.include "utils.asm"