Assemblage - Récursivité

Une procédure récursive est une procédure qui s'appelle elle-même. Il existe deux types de récursions: directe et indirecte. En récursivité directe, la procédure s'appelle elle-même et en récursivité indirecte, la première procédure appelle une seconde procédure, qui à son tour appelle la première procédure.

La récursivité a pu être observée dans de nombreux algorithmes mathématiques. Par exemple, considérons le cas du calcul de la factorielle d'un nombre. La factorielle d'un nombre est donnée par l'équation -

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

Par exemple: factorielle de 5 est 1 x 2 x 3 x 4 x 5 = 5 x factorielle de 4 et cela peut être un bon exemple montrant une procédure récursive. Chaque algorithme récursif doit avoir une condition de fin, c'est-à-dire que l'appel récursif du programme doit être arrêté lorsqu'une condition est remplie. Dans le cas de l'algorithme factoriel, la condition de fin est atteinte lorsque n vaut 0.

Le programme suivant montre comment factoriel n est implémenté en langage assembleur. Pour garder le programme simple, nous allons calculer factoriel 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

Lorsque le code ci-dessus est compilé et exécuté, il produit le résultat suivant -

Factorial 3 is:
6