彙編 - 遞迴

遞迴過程是指呼叫自身的過程。遞迴分為兩種：直接和間接。直接遞迴中，過程呼叫自身，間接遞迴中，第一個過程呼叫第二個過程，而第二個過程又呼叫第一個過程。

遞迴可以在很多數學演算法中觀察到。例如，考慮計算一個數的階乘的情況。一個數的階乘由如下公式給出 -

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

例如：5 的階乘為 1 x 2 x 3 x 4 x 5 = 5 x 4 的階乘，這可以很好地展示一個遞迴過程。每個遞迴演算法必須有一個終止條件，即當某個條件滿足時，程式的遞迴呼叫應該停止。對於階乘演算法，當 n 為 0 時達到終止條件。

以下程式展示瞭如何在組合語言中實現 n 的階乘。為了讓程式保持簡單，我們將計算 3 的階乘。

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

   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