1

所以我有这个计算阶乘的代码（通常），但在这个例子中它计算了 10 的阶乘

    .data 0x10008000
    .word 10
    .word 1
    .word 0
    .ascii "The factorial of 10 is %d \n"
    .text
    .globl main
main:
    addi $sp, $sp, -32
    sw $ra, 20($sp)
    sw $fp, 16($sp)
    addiu $fp, $sp,28
    lw $a0, 0($gp)
    jal fact

    ...

    lw $ra, 20($sp)
    lw $fp, 16($sp)
    addiu $sp, $sp, 32
    jr $ra
fact:
    addiu $sp, $sp, -32
    sw $ra, 20($sp)
    sw $fp, 16($sp)
    addiu $fp, $sp, 28
    sw $a0, 0($fp)
    lw $v0, 0($fp)      
    lw $t0, 4($gp)
    slt $t1,$v0,$t0     
    bne $t0, $t1, L2    
    addi $v0, $v0, 1
    jr L1
 L2:
    lw $v1, 0($fp)
    addi $v0, $v1, -1
    sw $v0, 8($gp)
    lw $a0, 8($gp)
    jal fact                   
    lw $v1, 0($fp)      
    mul $v0, $v0, $v1    
 L1:
    lw $ra, 20($sp)
    lw $fp, 16($sp)
    addiu $sp, $sp, 32
    jr $ra

我的问题是这不需要 l2 乘法后的 jr L1 命令吗？递归是如何工作的？它不需要某种方式来存储以前的数字吗？我认为这是堆栈的工作，但在我看来，每次调用该函数时，先前存储的变量都会被覆盖。

ps 我不知道是否有人理解我的问题我很抱歉我的英语不好......

4

2 回答 2

2

你的fact函数的工作方式是这样的：

int fact(unsigned int n) {
  if (n < 1) {
    return n+1;
  } else {
    return fact(n-1) * n;
  }
}

如您所见，它递归调用自身，直到参数变为< 1，此时它返回1（即0+1）并返回调用链以执行乘法。

例如，如果您这样做fact(3);了，调用链将如下所示：

fact(3): fact(2) * 3
  fact(2): fact(1) * 2
    fact(1): fact(0) * 1
      fact(0): 1
      1
    * 1 (==1)
  * 2 (==2)
* 3 (==6)

函数的值在 中返回$v0。n为了获得执行乘法的当前值fact(n-1) * n，该函数将其存储在当前堆栈帧 ( sw $a0, 0($fp)) 中，并在乘法之前将其读回 ( lw $v1, 0($fp))。
正如 Michael Burr 所评论的，在fact. 这就是前 4 条指令fact所做的（在堆栈上保留一些空间，保存当前帧指针和返回地址，并将帧指针指向新的堆栈帧）。

不需要L1在乘法之后跳转，因为L1它紧随其后（即无论如何都会到达标签）。

于 2013-05-13T05:34:14.760 回答
0

递归需要引入“手动堆栈管理”，这显然需要一些努力来实现。由于各种原因，并非所有编译器都支持它

这一切都发生在堆栈上，堆栈在不同的参数树之间扩展和收缩，这是一件非常令人惊奇的事情

如果您想“了解那些东西”，我建议您对“河内之塔”进行一些研究，这是一个高度递归的现实世界问题

这里有一个很好的解释

http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html

一旦你理解了递归，它就可以用来解决相当复杂的问题，比如数独求解器

一个典型的数独有大约 20 到 30 种不同的场景

因此，可以通过生成一个递归解决方案来规避 20 多个手动场景的编程，该解决方案也可以神奇地适用于“不可能”的 sudokos

于 2013-05-12T23:43:20.760 回答