assembly - MIPS汇编中的递归和迭代有什么区别

Question

我被要求在 MIPS 汇编中实现一个特定的算法，并且所述算法恰好有两种可能的实现 - 递归和迭代。我们的教授明确指出，我们的实现应该是递归的(不是因为它更好，它只是与我们涵盖的 Material 相关)。

我的问题是我不太明白递归过程和迭代过程在这种级别上的区别。循环和递归都是使用跳转实现的(据我所知)——你跳回到过程的开始，直到你到达某种基本情况。我的教授目前不在，所以我向你们寻求帮助 - 为了使您的程序递归而不是迭代，您需要做什么？什么时候跳回过程的顶部算迭代，什么时候算递归？

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