MIPS彙編：理解遞歸

Question

所以我有這樣的代碼 其計算階乘（一般） 但在這個例子中計算的10

.data 0x10008000 
    .word 10 
    .word 1 
    .word 0 
    .ascii "The factorial of 10 is %d \n" 
    .text 
    .globl main 
main: 
    addi $sp, $sp, -32 
    sw $ra, 20($sp) 
    sw $fp, 16($sp) 
    addiu $fp, $sp,28 
    lw $a0, 0($gp) 
    jal fact 

    ... 

    lw $ra, 20($sp) 
    lw $fp, 16($sp) 
    addiu $sp, $sp, 32 
    jr $ra 
fact: 
    addiu $sp, $sp, -32 
    sw $ra, 20($sp) 
    sw $fp, 16($sp) 
    addiu $fp, $sp, 28 
    sw $a0, 0($fp) 
    lw $v0, 0($fp)  
    lw $t0, 4($gp) 
    slt $t1,$v0,$t0  
    bne $t0, $t1, L2  
    addi $v0, $v0, 1 
    jr L1 
L2: 
    lw $v1, 0($fp) 
    addi $v0, $v1, -1 
    sw $v0, 8($gp) 
    lw $a0, 8($gp) 
    jal fact     
    lw $v1, 0($fp)  
    mul $v0, $v0, $v1  
L1: 
    lw $ra, 20($sp) 
    lw $fp, 16($sp) 
    addiu $sp, $sp, 32 
    jr $ra 

階乘我的問題是這樣的 不Ι需要一個 jr L1 命令後在L2中的乘法？ 遞歸如何工作？ 它不需要一些方法來存儲以前的數字？ 我認爲這是堆棧的工作，但在我看來，每次調用 的函數都會調用先前存儲的變量ars覆蓋。

PS如果任何人都瞭解我的問題 我爲我的英文不好對不起，我不知道......

Answer 1

您fact功能的工作原理是這樣的：

int fact(unsigned int n) { 
    if (n < 1) { 
    return n+1; 
    } else { 
    return fact(n-1) * n; 
    } 
} 

正如你可以看到它重新諷刺地自稱自己，直到參數變成< 1，此時它返回1（即， 0+1）並返回呼叫鏈執行乘法。

舉例來說，如果你沒有fact(3);，調用鏈是這樣的：

fact(3): fact(2) * 3 
    fact(2): fact(1) * 2 
    fact(1): fact(0) * 1 
     fact(0): 1 
     1 
    * 1 (==1) 
    * 2 (==2) 
* 3 (==6) 

在$v0返回函數的值。爲了獲得n的當前值以執行乘法fact(n-1) * n，該功能將其存儲在當前堆棧幀（sw $a0, 0($fp)）上並在乘法之前將其讀回（lw $v1, 0($fp)）。
正如Michael Burr所說，在fact的每個條目上都會創建一個新的堆棧幀。 fact的前4條指令就是這樣做的（在棧上保留一些空間，保存當前幀指針和返回地址，並將幀指針指向新的棧幀）。

自從L1緊跟在乘之後（即無論如何將會到達標籤），乘法之後不需要跳到L1。

Answer 2

遞歸需要引入「手工堆管理」，這顯然需要一些努力來實現。 並非所有的編譯器都支持它以各種理由

這一切都發生了哪些擴展和不同的參數樹之間的合同，是相當觀察

如果你想「瞭解的東西：」我一個了不起的事情在堆棧上建議你做一些研究的是一個高度遞歸現實世界中的問題

「河內塔」這裏有一個很好的解釋

http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html

一旦你理解了遞歸可用於相當複雜的問題，比如數獨解算器

一個典型的數獨遊戲有大約20到30個不同的場景

所以編程爲20+手動場景可以生產單一的遞歸規避解決方案，也神奇地適用於「不可能」 sudokos