Case Study: Recursive Functions

Introduction

"Classic" recursion attempts to solve a "big" problem by solving smaller versions of the problem, then using the solutions to the smaller versions of the problem to solve the big problem.

"Classic" recursion is a divide-and-conquer method. For example, consider merge sorting. The idea behind merge sorting is to divide an array into two halves, and sort each half. Then, you "merge" the two sorted halves to sort the entire list.

Thus, to solve the big problem of sorting an array, solve the smaller problem of sorting part of an array, and use the solution of the smaller sorted array to solve the big problem (by merging).

How do you solve the smaller version of the problem? You break that smaller problem into even smaller problems, and solve those.

Eventually, you get to the smallest sized problem, which is called the base case. This can be solved without using recursion.

Recursion allows you to express solutions to a problem very compactly and elegantly. This is why people like using recursion.

However, recursion can use a lot of stack, and if you're not careful, you can overflow the stack.

For recursion to be successful, the problem needs to have a recursive substructure. This is a fancy term that says that to solve a big problem (say of size N), you should be able to solve a smaller problem (of smaller size) in exactly the same way, except the problem size is smaller.

As an analogy, you might have to, say, sweep the floor. Sweeping half the floor is the same as sweeping the entire floor, except you do it on a smaller area. A problem that is solved recursively generally needs to have this property.

It's the Same!

The biggest misconception is that a function calls a smaller and smaller version, reaches the base case, then quits. For example, you might call fact(3), which calls fact(2), which calls fact(1), which finally calls fact(0), the base case.

Some programmers think the function stops there, right at the base case, and then jumps back to the initial recursive call. But you know that's not true.

Or do you? Suppose we have function f(), which calls function g(), and g() calls h().

What happens when we're done with h()? We return back to g(). And what happens when we're done with g()? We return back to f().

Recursive functions behave that way too! Thus, fact(3) calls fact(2) which calls fact(1) which calls fact(0), the base case. I call this phase the winding of the stack.

Once fact(0) is done, it goes back to fact(1), just like it would for non-recursive functions. When fact(1) is done, it goes back to fact(2). When fact(2) is done, it goes back to fact(3). When fact(3) is done, it goes back to whoever called fact(3). I call this the "unwinding" of the stack.

During the winding of the stack, you are making progress towards the base case. Basically, you're trying to get to the base case, solve the base case, and slowly grow your solution back as you go though the unwinding part of the recursion. Thus, winding heads to the solution of the base case, while unwinding typically grows the solution from base case back to the original call.

An Example

int sum( int arr[], int size ) {
   if ( size == 0 )
      return 0 ;
   else
      return sum( arr, size - 1 ) + arr[ size - 1 ] ;
}

A MIPS Translation

We have to decide what to save to the stack. We have two choices. Either save size - 1, from which we can compute arr[ size - 1 ], or save arr[ size - 1 ]. Let's opt to save size - 1 on the stack.

We must also save the return address, $ra since there is a function call. It's usually easy to tell whether to save the return address to the stack. If there's a function call, then save it.

sum:    addi $sp, $sp, -8       # Adjust sp
        addi $t0, $a0, -1       # Compute size - 1
        sw   $t0, 0($sp)        # Save size - 1 to stack
        sw   $ra, 4($sp)        # Save return address
        bne  $a0, $zero, ELSE   # branch ! ( size == 0 )
        li   $v0, 0             # Set return value to 0
        addi $sp, $sp, 8        # Adjust sp
        jr $ra                  # Return

ELSE:   move  $a1, $t0          # update second arg  
        jal   sum 
        lw    $t0, 0($sp)       # Restore size - 1 from stack
        li    $t7, 4            # t7 = 4 
        mult  $t0, t7           # Multiple size - 1 by 4 
        mflo  $t1               # Put result in t1 
        add   $t1, $t1, $a0     # Compute & arr[ size - 1 ]
        lw    $t2, 0($t1)       # t2 = arr[ size - 1 ]
        add   $v0, $v0, $t2     # retval = $v0 + arr[size - 1]
        lw    $ra, 4($sp)       # restore return address from stack         
        addi $sp, $sp, 8        # Adjust sp
        jr $ra                  # Return

There's nothing wrong to avoid moving the stack for the base case, however.

Notice in the ELSE, we copy size - 1, which is in $t0 to $a0. We didn't retrieve it from the stack. Why not? Because up to this point, we've made no subroutine call. Thus, $t0 still contains size - 1.

A Second Example

int sumOdd( int arr[], int size ) {
   if ( size == 0 )
      return 0 ;
   else if ( arr[ size - 1 ] % 2 == 1 )
      return sumOdd( arr, size - 1 ) + arr[ size - 1 ] ;
   else
      return sumOdd( arr, size - 1 ) ;
}

A MIPS Translation

So, let's save size - 1 and $ra to the stack. It turns out we also need to save arr[ size - 1 ] to the stack too.

sumOdd: addi $sp, $sp, -12      # Adjust sp
        addi $t0, $a0, -1       # Compute size - 1
        sw   $t0, 0($sp)        # Save size - 1 to stack
        sw   $ra, 4($sp)        # Save return address
        bne  $a0, $zero, ELSE2  # branch !( size == 0 )
        li   $v0, 0             # Set return value to 0
        addi $sp, $sp, 12       # Adjust sp
        jr   $ra                # Return

ELSE2:  li    $t7, 4            # t7 = 4 
        multi $t0, t7           # Multiple size - 1 by 4 
        mflo  $t1               # Put result in t1 
        add   $t1, $t1, $a0     # Compute & arr[ size - 1 ]
        lw    $t2, 0($t1)       # t2 = arr[ size - 1 ]
        andi  $t3, $t2, 1       # is arr[ size - 1 ] odd
        beq   $t3, $zero, ELSE3 # branch if even 
        sw    $t2, 8($sp)       # save arr[ size - 1 ] on stack 
        move  $a1, $t0          # update second arg  
        jal   sumOdd 
        lw    $t2, 8($sp)       # restore arr[ size - 1 ] from stack 
        add   $v0, $v0, $t2     # update return value 
        lw    $ra, 4($sp)       # restore return address from stack         
        addi  $sp, $sp, 12      # Adjust sp
        jr    $ra               # Return

ELSE3:  move  $a1, $t0          # update second arg  
        jal   sumOdd 
        lw    $ra, 4($sp)       # restore return address from stack         
        addi  $sp, $sp, 12      # Adjust sp
        jr    $ra               # Return

A few comments:

• In ELSE2, we use mult. The result is placed in two registers HI and LO. Since the number is likely to be quite small, we can assume the result is in LO, and HI contains all 0's. We can access the low word from LO, using mflo (move from LO).
• Note that using mult to multiply by 4 is generally a slow instruction compared to the doubling a value twice, or logical left shifting by 2 bits.
• In ELSE2 we need to access arr[ size - 1 ]. This then has to be placed on the stack because we'll need to use the value after the jal call.
• We use andi (bitwise and immediate) to test for even or odd. Essentially we mask all but the least significant bit and test if that value is 0 or 1. Fortunately, this trick works for UB and 2C representations.
• ELSE3 is quite short because we don't access the array elements. We don't even need to worry about $v0 because the call to jal sumOdd fills it in for us. All we have to do is to restore the return address and jump back.
• Array access tends to bloat the length of recursive function code in assembly language.

Summary

The main difference is jal does not call the same function. It calls a different one. However, it's all pretty much the same after that. The best way to see this is to write a non-recursive function in C, with helper functions, then translate it back.

Web Accessibility