MIPS汇编递归实现组合数n choose k异常：结果恒为1求助

你的代码存在几个关键问题，导致结果始终为1：

• 根本没执行计算逻辑：main函数里把jal nChooseK注释掉了，跳过了组合数计算步骤，直接执行打印。此时$v0没有被计算函数赋值，后续打印的是无效值（这里恰好显示1）。
• 递归参数传递错误：计算n-1 choose k-1时，你算出了$t0 = n-1、$t1 = k-1，但没把这两个值赋值给参数寄存器$a0和$a1就调用递归，导致每次递归传的还是原n和k，直接触发基准情况返回1。
• 函数缺少返回指令：return_1分支里设置$v0=1后，没有jr $ra指令，程序会继续往下跑，流程完全混乱。
• n-1 choose k参数传错：这一步应该把$a0设为n-1，$a1保持原k不变，但你写的是无意义的move $a0, $a0和错误的move $a1, $t1，参数完全不对。

修正后的代码 #

# Calculate n choose k
#
# n: integer value for n
# k: integer value for k
#
# Return: integer value for n choose k

.text
.globl nChooseK

nChooseK:
    # 递归前保存寄存器到栈，避免被覆盖
    addi $sp, $sp, -12
    sw $ra, 0($sp)
    sw $a0, 4($sp)
    sw $a1, 8($sp)

    # 基准情况：k=0或k=n时返回1
    beq $a1, $zero, return_1
    beq $a1, $a0, return_1

    # 计算 C(n-1, k-1)
    sub $a0, $a0, 1
    sub $a1, $a1, 1
    jal nChooseK
    move $t2, $v0

    # 恢复原n和k，准备计算 C(n-1, k)
    lw $a0, 4($sp)
    lw $a1, 8($sp)

    # 计算 C(n-1, k)
    sub $a0, $a0, 1
    jal nChooseK
    move $t3, $v0

    # 结果相加
    add $v0, $t2, $t3
    # 恢复寄存器并返回
    lw $ra, 0($sp)
    addi $sp, $sp, 12
    jr $ra

return_1:
    li $v0, 1
    # 恢复寄存器并返回
    lw $ra, 0($sp)
    lw $a0, 4($sp)
    lw $a1, 8($sp)
    addi $sp, $sp, 12
    jr $ra

# 主函数：打印组合数结果
.globl main

main:
    li $a0, 5     # 赋值n=5
    li $a1, 3      # 赋值k=3
    jal nChooseK   # 调用组合数计算函数
    move $a0, $v0  # 将结果存入$a0用于打印
    li $v0, 1      # 设置系统调用为打印整数
    syscall        # 执行打印
    
    li $v0, 10     # 设置系统调用为退出程序
    syscall        # 退出

修正说明 #

1. 取消main函数中jal nChooseK的注释，确保执行计算逻辑。
2. 递归前后添加栈操作，保存和恢复$ra、$a0、$a1，避免递归调用覆盖这些关键寄存器的值。
3. 修正递归参数传递：计算C(n-1, k-1)时直接修改$a0和$a1；计算C(n-1, k)时先恢复原参数，再修改$a0为n-1。
4. 给return_1分支添加返回指令和栈恢复操作，保证函数能正确返回调用点。

内容的提问来源于stack exchange，提问作者Raducu Mihai