Assembly - Đệ quy

Thủ tục đệ quy là một thủ tục gọi chính nó. Có hai loại đệ quy: trực tiếp và gián tiếp. Trong đệ quy trực tiếp, thủ tục gọi chính nó và trong đệ quy gián tiếp, thủ tục đầu tiên gọi thủ tục thứ hai, lần lượt gọi thủ tục đầu tiên.

Đệ quy có thể được quan sát trong nhiều thuật toán toán học. Ví dụ, hãy xem xét trường hợp tính giai thừa của một số. Giai thừa của một số được cho bởi phương trình -

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

Ví dụ: giai thừa của 5 là 1 x 2 x 3 x 4 x 5 = 5 x giai thừa của 4 và đây có thể là một ví dụ điển hình về việc hiển thị một thủ tục đệ quy. Mọi thuật toán đệ quy phải có một điều kiện kết thúc, nghĩa là, lệnh gọi đệ quy của chương trình phải được dừng lại khi một điều kiện được đáp ứng. Trong trường hợp thuật toán giai thừa, điều kiện cuối đạt được khi n bằng 0.

Chương trình sau đây cho thấy cách giai thừa n được thực hiện trong hợp ngữ. Để giữ cho chương trình đơn giản, chúng ta sẽ tính giai thừa 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

Khi đoạn mã trên được biên dịch và thực thi, nó tạo ra kết quả sau:

Factorial 3 is:
6