MIPS——递归调用

嵌套过程

不调用其他过程的过程称为叶过程(leaf procedure)。如果所有过程都是叶过程，那么情况就很简单。但是某个过程可以调用其他过程，甚至调用的是自身的“克隆”。在调用非叶过程时使用寄存器需要十分小心。

例如，假设主程序将参数3存入寄存器a0,然后使用jal A调用过程A。再假设过程A通过jal B调用过程B，参数为7，同样存入a0。由于A尚未结束任务，所以在寄存器a0的使用上存在冲突。同样，在寄存器ra保存的返回地址也存在冲突，因为它现在保存着B的返回值。

我们必须采取措施阻止这类问题发生：

一个解决方法是将其他所有必须保存的寄存器压栈，就像将保存寄存器压栈一样。调用者将所有调用后还需的参数寄存器（a1~a3）或临时寄存器（t0~t9）压栈。被调用者将返回地址寄存器(ra)和被调用者使用的保存寄存器（a0~a7）都压栈。栈指针 sp 随这栈中的寄存器个数调整。到返回时，寄存器会从存储器中恢复，栈指针也会随着重新调整。

有关指令

1     jal  function   #set $ra to Program Counter(PC),then jump to statement at target addres

C语言代码

 1 #include<stdio.h>
 2 
 3 int factorial(int n);
 4 
 5 int main()
 6 {
 7     int n;
 8     scanf("%d", &n);
 9     int res = factorial(n);
10     printf("%d
",res);
11     return 0;
12 }
13 
14 int factorial(int n)
15 {
16     if (n < 1)  return 1;
17     else  return n * factorial(n - 1);
18 }

虽然在C语言中函数定义可以在main函数前，也可以在main函数后，但定义在main函数后似乎更接近MIPS风格（看下面的代码你就知道了）

MIPS代码

 1 .data
 2     prompt1: .asciiz "Enter the number
"
 3     prompt2: .asciiz "The factorial of n is:
"
 4 
 5 .text
 6     # Print prompt1
 7     li $v0, 4
 8     la $a0, prompt1
 9     syscall
10 
11     # Read integer
12     li $v0, 5
13     syscall
14 
15     # Call factorial
16     move $a0, $v0
17     jal factorial
18     move $a1, $v0 # save return value to a1
19 
20     # Print prompt2
21     li $v0, 4
22     la $a0, prompt2
23     syscall
24 
25     # Print result
26     li $v0, 1
27     move $a0, $a1
28     syscall
29 
30     # Exit
31     li $v0, 10
32     syscall
33 
34     ## Function int factorial(int n)
35     factorial:
36         ## YOUR CODE HERE
37         addi $sp,$sp,-8            #adjust stack for 2 items
38         sw   $ra,4($sp)            #save return address
39         sw   $a0,0($sp)            #save the argument n
40     
41         slti $t0,$a0,1             #if n < 1,then set $t0 as 1
42         beq  $t0,$zero,L1          #if equal,then jump L1
43                                    #above all,if n >= 1,then jump L1
44         #if(n < 1)
45         addi $v0,$zero,1            #return 1
46         addi $sp,$sp,8              #pop 2 items off stack
47         jr   $ra                    #return to caller
48         #else
49         L1:
50             add $a0,$a0,-1          #argument :n - 1
51             jal factorial           #call factorial with (n-1)
52         
53            lw   $a0,0($sp)          #restore argument n
54            lw   $ra,4($sp)          #restore address
55            addi $sp,$sp,8           #adjust stack pionter
56            mul  $v0,$a0,$v0         #return n * factorial(n-1)
57            jr   $ra                  return to caller
58     ## END OF YOUR CODE
59   #jr $ra

手绘调用栈：