在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