在MIPS汇编中，递归和迭代有什么区别？

Question

我被要求在MIPS汇编中实现特定的算法，该算法恰好有两种可能的实现方式-递归和迭代。我们的教授明确表示，我们的实现应该是递归的（不是因为它更好，而是与我们所涵盖的内容相关）。

我的问题是，在这个级别上，我不太理解递归过程和迭代过程之间的区别。就我所知，循环和递归都使用跳转来实现-直到达到某种基本情况为止，您会跳回过程的开头。我的教授目前不可用，因此我向你们寻求帮助-为了使您的过程递归而不是迭代，您需要做什么？何时跳回到过程的顶部算作迭代，何时算作递归？

- user3062734

---

一个函数调用（无论是递归还是非递归）肯定不仅仅只是“跳转”到所需的函数吧？ - user395760

你在学习递归之前就开始学习像汇编这样困难的东西了吗？ - Siyuan Ren

递归与迭代的问题与编程语言无关。 - lurker

C.R. 是的，我知道什么是递归，但只在高级语言中了解。我对汇编语言感到困惑，因为函数调用本质上是跳转到代码中的不同位置，执行该部分，然后跳回。如果您想要在函数内部调用其他函数，则需要在开始时将返回地址推入堆栈，然后在跳回时将其弹出。因此，当您有一个调用自身的递归函数时，由于函数调用本质上是跳转，您最终会跳回到函数顶部，这与循环非常相似。 - user3062734

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

- Michael