Assembly - Ricorsione

Una procedura ricorsiva è quella che chiama se stessa. Esistono due tipi di ricorsione: diretta e indiretta. Nella ricorsione diretta, la procedura chiama se stessa e nella ricorsione indiretta, la prima procedura chiama una seconda procedura, che a sua volta chiama la prima procedura.

La ricorsione potrebbe essere osservata in numerosi algoritmi matematici. Si consideri ad esempio il caso del calcolo del fattoriale di un numero. Il fattoriale di un numero è dato dall'equazione -

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

Ad esempio: fattoriale di 5 è 1 x 2 x 3 x 4 x 5 = 5 x fattoriale di 4 e questo può essere un buon esempio per mostrare una procedura ricorsiva. Ogni algoritmo ricorsivo deve avere una condizione finale, cioè la chiamata ricorsiva del programma dovrebbe essere interrotta quando una condizione è soddisfatta. Nel caso dell'algoritmo fattoriale, la condizione finale viene raggiunta quando n è 0.

Il seguente programma mostra come il fattoriale n è implementato in linguaggio assembly. Per mantenere il programma semplice, calcoleremo il fattoriale 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

Quando il codice precedente viene compilato ed eseguito, produce il seguente risultato:

Factorial 3 is:
6