递归Collatz函数转MIPS汇编遇异常，求正确实现方案
2026-7-4
递归Collatz函数的MIPS汇编实现问题排查与修复
问题背景
练习将C语言递归Collatz函数转换为MIPS汇编，已编写驱动代码，但自行实现的collatz汇编函数输出异常，实际输出为大整数，与预期不符。
原C代码
uint32_t collatz(uint32_t n, int d) { /* printf("%d\n", n);*/ if (n != 1) { if (n % 2) return collatz(3 * n + 1, d + 1); else { return collatz(n / 2, d + 1); } } return d; }
驱动代码（原版本）
.data arrow: .asciiz " -> " .text main: li $sp, 0x7ffffffc # initialize $sp # PROLOGUE subu $sp, $sp, 8 # expand stack by 8 bytes sw $ra, 8($sp) # push $ra (ret addr, 4 bytes) sw $fp, 4($sp) # push $fp (4 bytes) addu $fp, $sp, 8 # set $fp to saved $ra subu $sp, $sp, 12 # save s0 and s1 on stack before using them sw $s0, 12($sp) # push $s0 sw $s1, 8($sp) # push $s1 sw $s2, 4($sp) # push $s2 la $s0, xarr # load address to s0 main_for: lw $s1, ($s0) # use s1 for xarr[i] value li $s2, 0 # use s2 for initial depth (steps) beqz $s1, main_end # if xarr[i] == 0, stop. # save args on stack rightmost one first subu $sp, $sp, 8 # save args on stack sw $s2, 8($sp) # save depth sw $s1, 4($sp) # save xarr[i] li $v0, 1 move $a0, $s1 # print_int(xarr[i]) syscall li $v0, 4 # print " -> " la $a0, arrow syscall jal collatz # result = collatz(xarr[i]) move $a0, $v0 # print_int(result) li $v0, 1 syscall li $a0, 10 # print_char('\n') li $v0, 11 syscall addu $s0, $s0, 4 # make s0 point to the next element lw $s2, 8($sp) # save depth lw $s1, 4($sp) # save xarr[i] addu $sp, $sp, 8 # save args on stack j main_for main_end: lw $s0, 12($sp) # restore $s0 lw $s1, 8($sp) # restore $s1 lw $s2, 4($sp) # restore $s2 # EPILOGUE move $sp, $fp # restore $sp lw $ra, ($fp) # restore saved $ra lw $fp, -4($sp) # restore saved $fp jr $ra # return to kernel
错误的collatz汇编实现
# collatz function in MIPS Assembly # Assumes n is in $a0 and d is in $a1 # Returns the result in $v0 .text .globl collatz collatz: addi $sp, $sp, -12 # Allocate stack space for local variables and return address sw $ra, 8($sp) # Save return address sw $a0, 4($sp) # Save n sw $a1, 0($sp) # Save d # Check if n is 1 (base case) li $t0, 1 beq $a0, $t0, base_case # Check if n is even or odd andi $t1, $a0, 1 # t1 = n % 2 beqz $t1, even_case # Odd case: 3n + 1 li $t2, 3 mul $t2, $a0, $t2 # t2 = 3 * n addi $t2, $t2, 1 # t2 = 3 * n + 1 j recursive_call even_case: # Even case: n / 2 srl $t2, $a0, 1 # t2 = n / 2 recursive_call: # Prepare arguments for recursive call lw $a0, 4($sp) # Restore n (冗余操作) lw $a1, 0($sp) # Restore d addi $a1, $a1, 1 # Increment d move $a0, $t2 # Update n jal collatz # Recursive call # Returning from recursive call j end_function base_case: # Base case: n is 1, return d lw $v0, 0($sp) # Load d into return value register $v0 end_function: lw $ra, 8($sp) # Restore return address addi $sp, $sp, 12 # Deallocate stack space jr $ra # Return to caller
实际异常输出
2 -> 2147476133 4 -> 2147476262 6 -> 2147476391 8 -> 2147476520 10 -> 2147476649
问题分析
- 参数传递错误：驱动代码中调用
collatz前，未将参数放入MIPS约定的$a0（n）和$a1（d）寄存器，而是错误地将参数压入栈中，导致collatz函数读取到垃圾值，输出异常大整数。 - 冗余代码：
collatz函数的recursive_call部分，先恢复原n到$a0，再立即用新n覆盖，属于冗余操作，虽不影响逻辑但可优化。
修正后的代码
修正后的驱动代码（关键部分修改）
移除不必要的参数压栈操作，调用前将参数放入约定寄存器：
main_for: lw $s1, ($s0) # use s1 for xarr[i] value li $s2, 0 # use s2 for initial depth (steps) beqz $s1, main_end # if xarr[i] == 0, stop. li $v0, 1 move $a0, $s1 # print_int(xarr[i]) syscall li $v0, 4 # print " -> " la $a0, arrow syscall # 传递参数到寄存器，符合MIPS调用约定 move $a0, $s1 # n = xarr[i] move $a1, $s2 # d = 0 jal collatz # result = collatz(n, d) move $a0, $v0 # print_int(result) li $v0, 1 syscall li $a0, 10 # print_char('\n') li $v0, 11 syscall addu $s0, $s0, 4 # make s0 point to the next element j main_for
修正后的collatz汇编函数
移除冗余操作，简化递归调用参数准备：
# collatz function in MIPS Assembly # n in $a0, d in $a1, returns result in $v0 .text .globl collatz collatz: addi $sp, $sp, -12 # Allocate stack space for ra, n, d sw $ra, 8($sp) # Save return address sw $a0, 4($sp) # Save current n sw $a1, 0($sp) # Save current d # Base case: n == 1, return d li $t0, 1 beq $a0, $t0, base_case # Check if n is even (n & 1 == 0) andi $t1, $a0, 1 beqz $t1, even_case # Odd case: compute 3*n +1 li $t2, 3 mul $t2, $a0, $t2 addi $t2, $t2, 1 j prepare_recurse even_case: # Even case: compute n/2 (logical shift right) srl $t2, $a0, 1 prepare_recurse: # Prepare recursive call arguments move $a0, $t2 # New n is t2 addi $a1, $a1, 1 # d +=1 jal collatz # Recursive call, result in $v0 j cleanup base_case: lw $v0, 0($sp) # Return d as result cleanup: lw $ra, 8($sp) # Restore return address addi $sp, $sp, 12 # Deallocate stack jr $ra # Return to caller
验证结果
修正后运行，输出符合预期：
2 -> 1 4 -> 2 6 -> 8 8 -> 3 10 -> 6
内容的提问来源于stack exchange，提问作者HelpNeeded
相关产品推荐
相关产品推荐
