Recursion

A recursive procedure is a nested procedure which calls itself. Most recursive procedures are based on inductive definitions, which consist of two parts:

1. Base Case;
2. Recursive Definition.

The power function, which raises a number B to a positive integer power N is defined by:

where indicates multiplication. A Pascal function may be written using a loop to evaluate the product iteratively:

Function Power(N, B: integer): integer;
{ Calculates B to Nth power iteratively }
    var I, Product: integer;
    begin { Power }
        Product := 1
        for I := 1 to N do
            Product := Product * B;
        Power := Product;
    end;  { Power }

Note that the product calculated in the procedure is returned by assigning Product to Power, the name of the function.

The same function may be defined recursively as:

In Pascal, the recursive power function can be written as:

Function Power(N, B: integer): integer;
{ Calculates B to Nth power recursively }
    begin { Power }
        if (N <= 0) then
            Power := 1
        else
            Power := B * Power(N-1,B);
    end;  { Power }

To implement the Power procedure in MAL, the nested procedure techniques for saving registers (including $ra) and parameters must be used.

Suppose the Power function has two parameters, N and B, which are passed on the stack and the function returns its result in $v0. Assume that the parameters N and B are initially in registers $a0 and $a1, respectively.

The MAL code to call the function and print the result is:

            .
            .
        add     $sp, -8 # push N and B on stack
        sw      $a0, 4($sp)
        sw      $a1, 8($sp)
        jal     Power   # call procedure
        add     $sp, 8  # pop parameters
        move    $4, $2  # move result for printing
        puti    $4      # print function result

The function below implements a recursive Power function. When the function calls itself recursively, it must follow the established conventions for passing parameters on the stack:

# function to calculate B to the Nth power recursively
#   returns:    $v0
#   parameters: B (on stack)
#               N (on stack)
#   registers:  $a0 -- N
#               $a1 -- B
Power:  sw      $ra, ($sp)   # save return address on stack
        add     $sp, -4 
        lw      $a0, 8($sp)  # load N from stack
        lw      $a1, 12($sp) # load B from stack
        bgtz    $a0, Induct  # if N>0, recursive case
        li      $v0, 1       # base case: return(1)
        b       Return
Induct:         # recursive case
        sub     $a0, 1       # N <- N-1
        add     $sp, -8      # push N and B on stack
        sw      $a0, 4($sp)
        sw      $a1, 8($sp)
        jal     Power        # call Power(N-1, B)
        add     $sp, 8       # pop parameters
        lw      $a1, 12($sp) # restore B
        mul     $v0,$v0,$a1  # return(B*Power(N-1, B))
Return: add     $sp, 4       # restore return address
        lw      $ra, ($sp)
        jr      $ra          # return

Any recursive algorithm can be implemented iteratively and vice-versa. Nonrecursive algorithms are usually faster because they doesn't have the overhead of the recursive procedure calls.