abc Asembler - elektronski priručnik
XVIII dio Rekurzija

Rekurzija

Rekurzivna procedura je ona koja poziva samu sebe. Postoje dve vrste rekurzije: direktna i indirektna. U direktnoj rekurziji, procedura poziva samu sebe, a u indirektnoj rekurziji, prva procedura poziva drugu proceduru, koja zatim poziva prvu proceduru.
Rekurzija se može primijetiti u brojnim matematičkim algoritmima. Na primjer, razmotrimo slučaj izračunavanja faktorijela nekog broja. Faktorijel broja je dat jednačinom:

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

Na primjer: faktorijel od 5 je 1 x 2 x 3 x 4 x 5 = 5 x faktorijel od 4 i to može biti dobar primjer da se pokaže rekurzivna procedura. Svaki rekurzivni algoritam mora imati završni uslov, tj., rekurzivno pozivanje programa se mora zaustaviti kada je uslov ispunjen. U slučaju algoritma za faktorijel, završni uslov je dostignut kada je n jednako 0.
Sljedeći program pokazuje kako je faktorijel n implementiran u asemblerskom jeziku. Da bi program ostao jednostavan, izračunaćemo faktorijel 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   'Faktorijel 3 je:',  0xa
len      equ $ - msg

section   .bss
fact  resb  1

Kada se gore navedeni kod kompajlira i izvrši, on će proizvesti sljedeći rezultat:

Faktorijel 3 je:
6

Stek kao struktura podataka    <    Index    >    Makroi