Subprograme recursive

Subprograme recursive

Subprogramele normale pot apela alte subprograme, dar nu se pot apela pe ele insele, fie direct, fie indirect prin alte subprograme pe care le apeleaza.

Subprogramele recursive permit ca in secventa de definitie (sau in subprogramele apelate) sa se apeleze pe ele insele. Apelul se face inainte de a se termina procedura.

Exista aplicatii care pot fi rezolvate prin algoritmi iterativi sau/si algoritmi iterativi. La apelarea subprogramului nu ne intereseaza ce tip de algoritm se utilizeaza. Ne intereseaza ca rezultatul obtinut sa fie corect.

Functia factorial are atat o definitie iterativa cat si una recursiva.

• Definitia iterativa este un ciclu de N inmultiri:

N! = 1*2*3*4*5*6*..*N

Algoritmul iterativ ce poate fi folosit este:

F=1 F=F * I pentru I=1.N

Definitia recursiva se bazeaza pe valoarea functiilor anterioare care nu sunt cunoscute

N! = N*(N-1)! cunoscand ca 1! =1, care este conditia de iesire din ciclul recursiv

Se scrie programul principal, care transmite in AX valoarea lui N, iar procedura Fact va returna in AX rezultatul N!.

S-a facut o exemplificare grafica a algoritmului pentru N=5.

La intrarea in procedura vom gasi in stiva adresa de revenire notata C2.

In procedura se decrementeaza AX si se cheama recursiv procedura Fact.

La fiecare Call de procedura se pune in stiva adresa de revenire C3.

Cand AX=1 se sare la eticheta C1 unde se initializeaza AX=1!=1 si BX=I=1.

Prin RET se revine la adresa din varful stivei C3 unde se face BX=I+1=2 si se calculeaza 2!.

Prin RET se revine la C3 unde se calculeaza BX=I+1=3 si AX=I*2!=3!

Prin RET se revine la C3 unde se calculeaza BX=I+1=4 si AX=I*3!=4!

Prin RET se revine la C3 unde se calculeaza BX=I+1=5 si AX=I*4!=5!

Prin urmatorul RET se revine la C2 in programul principal si AX=5!

; Program recursiv pentru calcul factorial

; Intrare AX=N Iesire AX=N!

Pfact Segment 'code'

assume cs:pfact,ds:sdate,ss:stiva

st1: mov ax,sdate ; initializare registre segment

mov ds,ax

mov ax,stiva

mov ss,ax

mov sp,offset top ; initializare stiva

mov ax,n ; AX=N pregatire apel subprogram

call Fact ; chemare subprogram recursiv N!

c2: mov f1,ax ; F1= N! memorare rezultat din AX

int 3 ; terminare program

mov ax,4c00h

int 21h

; Procedura recursiva calcul N!

Fact Proc near |

dec ax |

jz c1 ; N=1 si 1!=1 N | Stiva BX AX

call Fact ; apel recursiv |

c3: inc bx ; N=N+1 1 | C3 1 1!

imul bx ; N!=N*(N-1)! 2 | C3 2 2!

ret ; revenire 3 | C3 3 3!

c1: mov ax,1 ; 1!=1 4 | C3 4 4!

mov bx,1 ; N=1 SP 5 | C2 5 5!

ret ; revenire

Fact endp

Pfact ends

Sdate Segment 'data' ; segment de date

f1 dw 0

n dw 5

Sdate ends

stiva Segment 'stack' ; segment de stiva

dw 256 dup(?)

top equ $

stiva ends

end st1

Daca se transmite prin stiva si valoarea lui N la fiecare apel recursiv, atunci procedura PFACT se modifica, fara a modifica programul principal.

In acest caz evolutia stivei este cea din figura urmatoare. Este o succesiune de adrese de revenire si de valori ale lui N la chemarea procedurii.

FACT  PROC

CMP AX,1

JZ GATA ; N=1 si 1!=1

PUSH AX

DEC AX ; N=N-1

CALL FACT ; apel recursive

C3: POP BX ;N=N+1

IMUL BX ;N! = N*(N-1) !

GATA : RET

FACT  ENDP

Se observa ca desi exista un singur RET efectul lui este diferit, fiindca el face un salt la o adresa din varful stivei, care depinde de structura stivei.