Mips/assembly language exponentiation recursivley

Question

Im trying to implement this code in into assembly language. Im having trouble trying to solve this with idea of saving the both inputs from the user to the stack.

Here is the code for a recursive operation:

#include <iostream>
using namespace std;

int recursiveFunction ( int base, int power);

int main(int argc, const char * argv[])
{
    int base = 0;
    int power = 0;
    int result = 0;
    
    std::cout << "Enter the base to compute the exponential equation";
    std::cout << endl;
    
    
    std::cin >> base;
    
    std::cout<< "Enter the power for the base to conduct solution";
    std::cout<< endl;
    
    std::cin>> power;
    
    result = recursiveFunction(base,power);
    
    std::cout<<"The result of the following calculation is:" << result;
    std::cout<<endl;
    std::cout<<endl;
    
return 0;
}

int recursiveFunction(int base, int power)
{
   if( power != 0)
   {
       return(base*recursiveFunction(base, (power - 1)));
       
   }
    else
    return 1;
}

Answer 1

When to use stack space:

As much as possible, we would prefer to map local variables (e.g. from algorithms in C/C++) to CPU registers, rather than stack locations; however, many registers won't survive a function call.  The stack is used to allocate call-related memory that will survive subsequent function calling.  Some registers do survive function calling but to be clear, that is ensured by using stack memory to preserve those registers' original values so they can be restored later.

We need to do an analysis on local variables to identify which ones need to survive a function call as these will need special treatment requiring stack memory.

For example, in main, we can be certain that power does not need to survive a function call.  The variable power is defined with initial value 0 but no one uses that — so we will ignore that initialization.  Next it is set with the return value from a syscall, and then immediately consumed as an argument to the recursive function — yet not used later, after the recursive call.  Thus, power does not need to survive a function call, and can simply be allocated to a temporary register (one that does not survive a function call).

A slight modification to the code, such as printing the power value after the recursive call, would render the opposite analysis.

The same analysis actually applies to all the variables in main, since technically, all the prompt and inputs are done via syscalls, which are not the same as regular function calls — in that they preserve even temporary registers except those involved in parameter passing and return values for their own operation: usually this means that $a0 and $v0 cannot be relied upon to survive the syscall, since they are usually part of the definition of the syscall parameter passing.  Yet the other temporary registers can be relied upon to survive a syscall.  So, you can use $t1, $t2, $t3, for base, power, result in main and without needing any stack space or memory loads & stores.  base does need to survive the prompt and input for power but as per above, those two operations are done with syscalls, rather than regular function calls, meaning that base also does not need a stack location.

The analysis to identify local variables that must survive a (non-syscall) function call is particularly important in recursiveFunction.  The base variable is defined as a parameter, and used after the function call (that happens to be recursive).  It is used as an operand to multiplication, whose other operand is the function call's return value.  For this analysis it doesn't matter that the function call inside recursiveFunction is itself recursive, as this analysis would not change if some other (non-recursive) function were called instead — the mere calling of another function is at issue.  Because it needs to survive the recursive call, it should be stored to stack memory (before the recursive call when its value is still available) and reloaded when needed (after the recursive call).

power does not need to survive the call inside recursiveFunction.  Thus, it should simply be decremented and that's all for it — no stack memory needed.

At their end, most non-main functions return to their caller.  This is accomplished by initially passing them a parameter of what code location to resume (transfer control to) when they are completed.  This parameter is hidden from view in higher level languages, but in MIPS is in the $ra register.  It is passed as a parameter and used at the very end of the function, in returning to its caller.  Thus, it must survive any function calling done by a function's implementation, as any function call itself repurposes that register (for its calling own activity).

Also, it is ok (correct, though perhaps inefficient) to use stack space when not needed, i.e. when a variable does not need to survive function call.

(I am aware that there are optimization opportunities but I feel they are not on topic at the moment.)

How to use stack space:

First, allocate some stack space: allocate as much as you want using addiu $sp, $sp, -X where X is a constant number whose value is 4 or larger and is also a multiple of 4.  Count up bytes in all the words you want and allocate them all with a single addiu instruction.

That newly allocated stack space will start at 0($sp).  If you allocated more than 4 bytes (e.g. 12 bytes) then you have 0($sp) (aka $sp+0) as the address of the first word and 4($sp), 8($sp) as successive available words.  These memory locations are yours to use for the duration of your function (e.g. main).  By "yours" I mean they belong to the activation of the function that allocated them for the duration of that activation.  (A recursive function may have multiple activations on the stack.)

You can make a mental mapping of the new stack locations to the local variables in the function, and use the corresponding memory location when the C/C++ code uses the corresponding variable.

Be sure to release the stack space before returning to a function's caller.  If you use syscall 10 to exit the program you don't need to release the space; however if you want to return to the caller you must restore the stack pointer to its original value prior to returning or else callers will not find their own stack-based variables, should they also use the stack.  This would be applicable to recursiveFunction, for example, if you also desire to use stack space there.

Space below the stack pointer is "unallocated" and free to be allocated and then used in this manner by any an all functions.  Stack space at and above the stack pointer is in use by the function call chain, and whichever functions allocated the space on entry must also release that same space upon exit.