Majelis - Rekursi

Prosedur rekursif adalah salah satu yang menyebut dirinya sendiri. Ada dua jenis rekursi: langsung dan tidak langsung. Dalam rekursi langsung, prosedur memanggil dirinya sendiri dan dalam rekursi tidak langsung, prosedur pertama memanggil prosedur kedua, yang pada gilirannya memanggil prosedur pertama.

Rekursi dapat diamati dalam berbagai algoritma matematika. Misalnya, pertimbangkan kasus penghitungan faktorial sebuah angka. Faktorial suatu angka diberikan oleh persamaan -

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

Contoh: faktorial 5 adalah 1 x 2 x 3 x 4 x 5 = 5 x faktorial dari 4 dan ini bisa menjadi contoh yang baik untuk menunjukkan prosedur rekursif. Setiap algoritma rekursif harus memiliki kondisi akhir, yaitu pemanggilan program rekursif harus dihentikan ketika kondisi terpenuhi. Dalam kasus algoritma faktorial, kondisi akhir tercapai ketika n bernilai 0.

Program berikut menunjukkan bagaimana faktorial n diimplementasikan dalam bahasa assembly. Agar program tetap sederhana, kita akan menghitung faktorial 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

Ketika kode di atas dikompilasi dan dijalankan, itu menghasilkan hasil sebagai berikut -

Factorial 3 is:
6