Ensamblaje - Recurrencia

Un procedimiento recursivo es aquel que se llama a sí mismo. Hay dos tipos de recursividad: directa e indirecta. En la recursividad directa, el procedimiento se llama a sí mismo y en la recursividad indirecta, el primer procedimiento llama a un segundo procedimiento, que a su vez llama al primer procedimiento.

La recursividad se pudo observar en numerosos algoritmos matemáticos. Por ejemplo, considere el caso de calcular el factorial de un número. El factorial de un número viene dado por la ecuación -

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

Por ejemplo: el factorial de 5 es 1 x 2 x 3 x 4 x 5 = 5 x factorial de 4 y este puede ser un buen ejemplo de cómo mostrar un procedimiento recursivo. Todo algoritmo recursivo debe tener una condición de finalización, es decir, la llamada recursiva del programa debe detenerse cuando se cumple una condición. En el caso del algoritmo factorial, la condición final se alcanza cuando n es 0.

El siguiente programa muestra cómo se implementa factorial n en lenguaje ensamblador. Para mantener el programa simple, calcularemos el factorial 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

Cuando se compila y ejecuta el código anterior, produce el siguiente resultado:

Factorial 3 is:
6