MIPS程序集中的递归和迭代之间有什么区别

Question

我已经在MIPS汇编中给出了一个特定的算法,并且所述算法碰巧有两种可能的实现 - 递归和迭代.我们的教授明确指出,我们的实现应该是递归的(不是因为它更好,它只与我们所涉及的材料相关).

我的问题是我不太了解递归过程和这种级别的迭代过程之间的区别.使用跳转实现循环和递归(据我所知) - 您跳回到过程的开始,直到达到某种基本情况.我的教授目前无法使用,所以我要求大家帮忙 - 为了使你的程序递归而不是迭代,你需要做什么？什么时候跳回到过程的顶部算作迭代,什么时候算作递归？

Answer 1

不同之处在于迭代版本只是循环,而递归版本将调用自身,从而建立一个"链"调用,最终减少调用以产生函数的结果.

假设您正在进行3的递归计算!(3阶乘).该过程看起来像这样:

fact(3) => return fact(2) * 3
   fact(2) => return fact(1) * 2
      fact(1) => This is the base case; return 1
   return 1 * 2 (== 2)
return 2 * 3 ( == 6)

以下是MIPS汇编中的交互式和递归因子函数的几个参考实现.请注意,我使用n == 0作为基本情况而不是n == 1,因为这更容易使用MIPS上提供的指令.

# Iterative n!
# In: $a0 = n
# Out: $v0 = n!
fact_iter:
  li $v0,1
_fact_iter_loop:
  beq   $a0,$zero,_fact_iter_return
  multu $v0,$a0
  mflo $v0
  addiu $a0,$a0,-1
  j _fact_iter_loop
_fact_iter_return:
  jr $ra


# Recursive n!
# In: $a0 = n
# Out: $v0 = n!
fact_recur:
    addiu $sp,$sp,-4    
    sw $ra,($sp)         # Save the current return address on the stack
    beq $a0,$zero,_fact_recur_base_case
    addiu $sp,$sp,-4
    sw $a0,($sp)         # Save the current argument (n) on the stack
    addiu $a0,$a0,-1
    jal fact_recur     # Call the function recursively with n-1 as the argument
    lw $a0,($sp)         # Restore the saved argument
    addiu $sp,$sp,4
    multu $v0,$a0       
    mflo $v0            # Set $v0 = n * (n-1)!
_fact_recur_return: 
    lw $ra,($sp)       # Restore the return address
    addiu $sp,$sp,4
    jr $ra
_fact_recur_base_case:
    li $v0,1
    j _fact_recur_return