MIPS/汇编语言求幂递归 [英] Mips/assembly language exponentiation recursivley
问题描述
我正在尝试用汇编语言实现此代码。我在尝试通过将用户的两个输入保存到堆栈的想法来解决此问题时遇到问题。
以下是递归操作的代码:
#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;
}
推荐答案
何时使用堆栈空间:
尽可能多地将局部变量(例如,来自C/C++中的算法)映射到CPU寄存器,而不是堆栈位置;然而,许多寄存器不会在函数调用中幸存下来。*堆栈用于分配与调用相关的内存,这些内存将在后续函数调用中幸存。"有些寄存器确实在函数调用中幸存下来,但要清楚一点,这是通过使用堆栈内存保留那些寄存器的原始值以便稍后可以还原来确保的。
我们需要对局部变量进行分析,以确定哪些变量需要在函数调用中幸存下来,因为这些变量需要特殊处理,需要堆栈内存。
例如,在main
中,我们可以确定power
不需要在函数调用后继续存在。由于变量power
定义为初始值0,但没有人使用该初始值,因此我们将忽略该初始化。接下来,使用syscall的返回值设置该变量,然后立即将其作为递归函数的参数使用-但在递归调用后不会在以后使用。因此,power
不需要在递归调用之后使用。因此,power
不需要在以后的递归调用之后使用。因此,power
不需要在递归调用之后使用。因此,power
不需要使用该初始化。因此,power
不需要并且可以简单地分配给临时寄存器(在函数调用后无法存活的寄存器)。
对代码稍作修改,如在递归调用后打印power
值,将呈现相反的分析。
main
中的所有变量,因为从技术上讲,所有的提示和输入都是通过syscall完成的,这与常规函数调用不同-因为它们甚至保留了临时寄存器,除了那些涉及参数传递和自己操作的返回值的寄存器:通常这意味着不能依赖和$v0
在syscall中幸存下来,因为它们通常是syscall参数传递的定义的一部分。然而,其他临时寄存器可以在syscall中幸存。因此,您可以在main
中使用$t1
、$t2
、$t3
、base
、power
、result
,而不需要任何堆栈空间或内存负载&;存储。base
不需要保留power
的提示和输入,但如上所述,这两个操作是通过syscall完成的,而不是常规的函数调用,这意味着base
也不需要堆栈位置。
分析确定必须在(非系统调用)函数调用中幸存下来的局部变量在recursiveFunction
中尤为重要。base
变量被定义为参数,并在函数调用(恰好是递归的)之后使用。它被用作乘法的操作数,其另一个操作数是函数调用的返回值。对于此分析,recursiveFunction
内部的函数调用本身是递归的并不重要。因为如果调用其他(非递归)函数,这种分析不会改变--只是调用另一个函数是有问题的。因为它需要在递归调用中幸存下来,所以它应该存储到堆栈内存中(当它的值仍然可用时,在递归调用之前),并在需要时重新加载(在递归调用之后)。
power
不需要保留recursiveFunction
内部的调用。因此,只需将其递减即可,仅此而已-不需要堆栈内存。
$ra
寄存器中。在返回给其调用者时,它被作为参数传递并在函数的最末尾使用。因此,它必须在函数的实现完成的任何函数调用中幸存下来,因为任何函数调用本身都会重用该参数。因此,它必须在函数的实现完成的任何函数调用中幸存下来,因为任何函数调用本身都会重用
另外,在不需要时(即当变量不需要保留函数调用时)使用堆栈空间也是可以的(正确的,但可能效率较低)。
(我知道有优化机会,但我觉得它们目前不是主题。)
如何使用堆栈空间:
首先,分配一些堆栈空间:使用addiu $sp, $sp, -X
随意分配,其中X是一个值大于或等于4的常量,也是4的倍数。请将您想要的所有字中的字节数加起来,并使用一条addiu
指令将其全部分配。
0($sp)
开始。如果分配的字节超过4个字节(例如,12个字节),则有0($sp)
(也称为$sp+0)作为第一个字的地址,4($sp)
,8($sp)
作为连续的可用字。这些内存位置由您在函数期间使用(例如,main
)。由";您的";我的意思是,它们属于在激活期间分配它们的函数的激活。)(递归函数可以在堆栈上有多次激活。)
您可以在心理上将新堆栈位置映射到函数中的局部变量,并在C/C++代码使用相应变量时使用相应的内存位置。
请确保在返回到函数的调用方之前释放堆栈空间。*如果使用syscall 10退出程序,则不需要释放空间;但是,如果要返回到调用方,则必须在返回之前将堆栈指针还原为其原始值,否则如果调用方也使用堆栈,则调用方将找不到自己的基于堆栈的变量。例如,如果您还希望在那里使用堆栈空间,则这将适用于recursiveFunction
。
堆栈指针下方的空间是";未分配的,可以自由分配,然后由任何一个和所有函数以这种方式使用。"堆栈指针及其上方的堆栈空间正在由函数调用链使用,任何在进入时分配空间的函数也必须在退出时释放相同的空间。
这篇关于MIPS/汇编语言求幂递归的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!