Page 47 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes 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
Notice that we could have tested the if-else statement right away, and not used the stack.
However, by adjusting the stack right away, it makes sure that we deal with the stack. So
that’s why we often have the saving of registers on the stack at the beginning even if the
base case might not require any adjustment of the stack.
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

Let’s solve the following variation of a recursive function, written in C. This sums only the
odd elements of an array.
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 ) ;
}

Contd...

40 LOVELY PROFESSIONAL UNIVERSITY