Assembly組合 遞回


遞迴過程呼叫本身。有兩種型別:直接和間接的遞迴。在直接遞回過程呼叫和間接遞回,第一個程式呼叫了第二個過程,這反過來呼叫的第一個程式。

遞回被發現許多的數學演算法。例如,考慮的情況下,計算一個數的階乘。一個數的階乘是由下式給出:

Fact (n) = n * fact (n-1) for n > 0

例如:5的階乘是1×2×3×4×5=5×4的階乘,並顯示一個遞迴的過程,這可能是一個很好的例子。每一個遞迴演算法必須有一個結束條件,即滿足某種條件時,應停止遞回呼叫的程式。階乘演算法結束條件的情況下,當n為0時,就結束了。

下面的程式顯示了如何階乘n的組合語言實現。為了保持程式簡單,我們將計算階乘3。

section	.text
    global _start         ;must be declared for using gcc
_start:    ;tell linker entry yiibai

    mov bx, 3       ;for calculating factorial 3
    call  proc_fact
    add   ax, 30h
    mov  [fact], ax
    
    mov	  edx,len   ;message length
    mov	  ecx,msg   ;message to write
    mov	  ebx,1     ;file descriptor (stdout)
    mov	  eax,4     ;system call number (sys_write)
    int	  0x80      ;call kernel

    mov   edx,1     ;message length
    mov	  ecx,fact  ;message to write
    mov	  ebx,1     ;file descriptor (stdout)
    mov	  eax,4     ;system call number (sys_write)
    int	  0x80      ;call kernel
    
    mov	  eax,1     ;system call number (sys_exit)
    int	  0x80      ;call kernel
proc_fact:
    cmp   bl, 1
    jg    do_calculation
    mov   ax, 1
    ret
do_calculation:
    dec   bl
    call  proc_fact
    inc   bl
    mul   bl        ;ax = al * bl
    ret

section	.data
msg db 'Factorial 3 is:',0xa	
len equ $ - msg			

section .bss
fact resb 1

上面的程式碼編譯和執行時,它會產生以下結果:

Factorial 3 is:
6