Proceduri recursive
Numim procedură recursivă o procedură care se autoapelează (direct sau indirect). Forma generală a unei
funcţii recursive este următoarea:
tip f(lista_parametri_formali){
if (!conditie_de_oprire){
...
... f(lista_parametri_reali)
...
}
}
Recursivitatea poate fi utilizată pentru a rezolva elegant multe probleme, dar procedurile recursive
sunt adesea mai lente decât corespondentele lor nerecursive:
• la fiecare apel se depun în stivă valorile parametrilor (dacă există) şi adresa de revenire
(vezi lucrarea de laborator nr. 6)
• complexitatea algoritmilor recursivi este de obicei mai mare decât a celor iterativi.
Aplicaţie
Enunţ :
Să se realizeze o funcţie recursivă ce calculează n!
Rezolvare :
Plecăm de la formula recursivă de calcul
⋅ − >
=
=
( ,)!1 0
,1 0
!
n n n
n
n cunoscută din liceu.
Rescriind formula într-o variantă mai apropiată de implementare, avem:
− >
=
=
* ( ),1 0
,1 0
( )
n fact n n
n
fact n
Pentru a înţelege mai uşor programul realizat în limbaj de asamblare, să urmărim pentru început programul
C, care declară o funcţie recursivă fact, citeşte de la tastatură o valoare, şi foloseşte funcţia pentru a returna
factorialul acestei valori:
#include <stdio.h>
long fact(int n){
if(n==0) return 1; //conditia de oprire
return n*fact(n-1) //apel recursiv: n!=n(n-1)!
}
void main(){
int n;
scanf("%d",&n); //citire n
printf("%ld",fact(n)); //afisare n!
}
Analiză:
La orice funcţie recursivă trebuie precizată o condiţie de ieşire. În problema factorialului, condiţia
de ieşire este 0! care, prin definiţie, este 1. Dacă parametrul primit de fact este 0, atunci funcţia returnează
1, altfel returnează rezultatul înmulţirii dintre valoarea parametrului şi factorialul apelat cu valoarea
parametrului minus 1.
Pentru fact(3) avem următoarea succesiune de operaţii:
(1) apelează recursiv fact(2);
(2) apelează recursiv fact(1);
(3) apelează recursiv fact(0);
(4) returnează 1 – revenire din fact(0), calculează 1*fact(0);
(5) returnează 1 – revenire din fact(1), calculează 2*fact(1);
(6) returnează 2 – revenire din fact(2), calculează 3*fact(2);
(7) returnează 6 – revenire din fact(3);
Implementarea programului în limbaj de asamblare este următoarea:
.model small
.stack
sablon struc
_bp dw ?
_cs_ip dw ?
_n dw ?
sablon ends
.data
n dw 7
rez dd ?
.code
fact proc near
push bp ;salvare bp
mov bp, sp ;initializare cu varful stivei
pushf ;salvare indicatori
push bx
mov bx, word ptr [bp]._n ;preluarea parametrului
cmp bx, 0 ;conditia de oprire
jne rec
mov ax, 1 ;0!=1
fact(3) {
if(n == 0) return 1;
return 3 * fact(3-1);
}
6
fact(2) {
if(n == 0) return 1;
return 2 * fact(2-1);
}
2
fact(1) {
if(n == 0) return 1;
return 1 * fact(1-1);
}
1
fact(0) {
if(n == 0)
return 1;
}
1
mov dx, 0
jmp stop
rec:dec bx ;termenul urmator
push bx ;transferul parametrului
call near ptr fact ;apel recursiv, cu rezultat in DX:AX
add sp, 2
mul word ptr [bp]._n
stop:pop bx ;refacerea registrului bx
popf ;refacere indicatori
pop bp
retn
fact endp
afis proc near
push ax ;salvarea registrelor
push bx
push cx
push dx
mov dx, word ptr rez+2 ;preluare din rez
mov ax, word ptr rez
mov cx, 0 ;initializarea contorului
mov bx, 10
next:div bx ;se obtine pe rand in dx fiecare cifra zecimala
push dx ;salvarea in stiva e necesara pentru afisarea in ordinea corecta
mov dx, 0
inc cx
cmp ax, 0
jne next
print:pop dx ;preluare din stiva
add dl, 30h ;conversie la codul ASCII
mov ah, 02h
int 21h ;afisare
loop print
pop dx ;refacerea registrelor
pop cx
pop bx
pop ax
retn
afis endp
start:
mov ax, @data ;initializare registru segment
mov ds, ax
mov ax, n
push ax ;transferul parametrului prin stiva
call near ptr fact ;DX:AX<--rezultatul
add sp, 2
mov word ptr rez+2, dx ;rezultatul se depune in rez
mov word ptr rez, ax
call near ptr afis ;afisarea rezultatului
mov ah, 4ch ;revenire DOS
int 21h
end start
Pentru preluarea parametrului din stivă, procedura fact foloseşte următoarea structură şablon:
sablon struc
_bp dw ?
_cs_ip dw ?
_n dw ?
sablon ends
Deoarece în problema factorialului, condiţia de ieşire este 0! care, prin definiţie, este 1, după preluarea
parametrului, valoarea acestuia se compară cu 0. În caz de egalitate, în DX:AX se depune valoarea 1 şi se
face salt la eticheta stop (procedura întoarce valoarea 1). Dacă valoarea parametrului nu este 0, se
returnează rezultatul înmulţirii dintre valoarea parametrului şi factorialul apelat cu valoarea parametrului
minus 1.
Să urmărim din nou succesiunea de operaţii pentru acelaşi exemplu (3!), apelăm deci procedura fact cu
valoarea 3 trimisă ca parametru:
(1) apelează recursiv procedura fact, valoarea parametrului este 2;
(2) apelează recursiv procedura fact, valoarea parametrului este 1;
(3) apelează recursiv procedura fact, valoarea parametrului este 0;
(4) returnează 1 în DX:AX – revenire din fact(0);
(5) returnează 1 în DX:AX – revenire din fact(1);
(6) returnează 2 în DX:AX – revenire din fact(2);
(7) returnează 6 în DX:AX – revenire din fact(3);
Procedura afis preia rezultatul din rez (rezultatul se depune în rez înainte de a apela procedura
afis), converteşte această valoare în zecimal şi o afişează.
2. Aplicaţii
1. Modificaţi programul prezentat, înlocuind procedura nerecursivă afis cu o procedură recursivă
Să se realizeze funcţii care rezolvă recursiv următoarele probleme:
2. Calculaţi
⋅ >
=
= −
2 2 , 0
,1 0
2
1
n
n
n
n
3. Calculaţi cel de-al n-lea număr Fibonacci
− + − >
=
=
=
( )1 ( ),2 1
,1 1
,0 0
( )
fibo n fibo n n
n
n
fibo n
4. Calculaţi
+
=
=
=
−
−
− C C in rest
k
n k
C
k
n
k
n
k
n
,
,1 0
,1
1
1
1.
Numim procedură recursivă o procedură care se autoapelează (direct sau indirect). Forma generală a unei
funcţii recursive este următoarea:
tip f(lista_parametri_formali){
if (!conditie_de_oprire){
...
... f(lista_parametri_reali)
...
}
}
Recursivitatea poate fi utilizată pentru a rezolva elegant multe probleme, dar procedurile recursive
sunt adesea mai lente decât corespondentele lor nerecursive:
• la fiecare apel se depun în stivă valorile parametrilor (dacă există) şi adresa de revenire
(vezi lucrarea de laborator nr. 6)
• complexitatea algoritmilor recursivi este de obicei mai mare decât a celor iterativi.
Aplicaţie
Enunţ :
Să se realizeze o funcţie recursivă ce calculează n!
Rezolvare :
Plecăm de la formula recursivă de calcul
⋅ − >
=
=
( ,)!1 0
,1 0
!
n n n
n
n cunoscută din liceu.
Rescriind formula într-o variantă mai apropiată de implementare, avem:
− >
=
=
* ( ),1 0
,1 0
( )
n fact n n
n
fact n
Pentru a înţelege mai uşor programul realizat în limbaj de asamblare, să urmărim pentru început programul
C, care declară o funcţie recursivă fact, citeşte de la tastatură o valoare, şi foloseşte funcţia pentru a returna
factorialul acestei valori:
#include <stdio.h>
long fact(int n){
if(n==0) return 1; //conditia de oprire
return n*fact(n-1) //apel recursiv: n!=n(n-1)!
}
void main(){
int n;
scanf("%d",&n); //citire n
printf("%ld",fact(n)); //afisare n!
}
Analiză:
La orice funcţie recursivă trebuie precizată o condiţie de ieşire. În problema factorialului, condiţia
de ieşire este 0! care, prin definiţie, este 1. Dacă parametrul primit de fact este 0, atunci funcţia returnează
1, altfel returnează rezultatul înmulţirii dintre valoarea parametrului şi factorialul apelat cu valoarea
parametrului minus 1.
Pentru fact(3) avem următoarea succesiune de operaţii:
(1) apelează recursiv fact(2);
(2) apelează recursiv fact(1);
(3) apelează recursiv fact(0);
(4) returnează 1 – revenire din fact(0), calculează 1*fact(0);
(5) returnează 1 – revenire din fact(1), calculează 2*fact(1);
(6) returnează 2 – revenire din fact(2), calculează 3*fact(2);
(7) returnează 6 – revenire din fact(3);
Implementarea programului în limbaj de asamblare este următoarea:
.model small
.stack
sablon struc
_bp dw ?
_cs_ip dw ?
_n dw ?
sablon ends
.data
n dw 7
rez dd ?
.code
fact proc near
push bp ;salvare bp
mov bp, sp ;initializare cu varful stivei
pushf ;salvare indicatori
push bx
mov bx, word ptr [bp]._n ;preluarea parametrului
cmp bx, 0 ;conditia de oprire
jne rec
mov ax, 1 ;0!=1
fact(3) {
if(n == 0) return 1;
return 3 * fact(3-1);
}
6
fact(2) {
if(n == 0) return 1;
return 2 * fact(2-1);
}
2
fact(1) {
if(n == 0) return 1;
return 1 * fact(1-1);
}
1
fact(0) {
if(n == 0)
return 1;
}
1
mov dx, 0
jmp stop
rec:dec bx ;termenul urmator
push bx ;transferul parametrului
call near ptr fact ;apel recursiv, cu rezultat in DX:AX
add sp, 2
mul word ptr [bp]._n
stop:pop bx ;refacerea registrului bx
popf ;refacere indicatori
pop bp
retn
fact endp
afis proc near
push ax ;salvarea registrelor
push bx
push cx
push dx
mov dx, word ptr rez+2 ;preluare din rez
mov ax, word ptr rez
mov cx, 0 ;initializarea contorului
mov bx, 10
next:div bx ;se obtine pe rand in dx fiecare cifra zecimala
push dx ;salvarea in stiva e necesara pentru afisarea in ordinea corecta
mov dx, 0
inc cx
cmp ax, 0
jne next
print:pop dx ;preluare din stiva
add dl, 30h ;conversie la codul ASCII
mov ah, 02h
int 21h ;afisare
loop print
pop dx ;refacerea registrelor
pop cx
pop bx
pop ax
retn
afis endp
start:
mov ax, @data ;initializare registru segment
mov ds, ax
mov ax, n
push ax ;transferul parametrului prin stiva
call near ptr fact ;DX:AX<--rezultatul
add sp, 2
mov word ptr rez+2, dx ;rezultatul se depune in rez
mov word ptr rez, ax
call near ptr afis ;afisarea rezultatului
mov ah, 4ch ;revenire DOS
int 21h
end start
Pentru preluarea parametrului din stivă, procedura fact foloseşte următoarea structură şablon:
sablon struc
_bp dw ?
_cs_ip dw ?
_n dw ?
sablon ends
Deoarece în problema factorialului, condiţia de ieşire este 0! care, prin definiţie, este 1, după preluarea
parametrului, valoarea acestuia se compară cu 0. În caz de egalitate, în DX:AX se depune valoarea 1 şi se
face salt la eticheta stop (procedura întoarce valoarea 1). Dacă valoarea parametrului nu este 0, se
returnează rezultatul înmulţirii dintre valoarea parametrului şi factorialul apelat cu valoarea parametrului
minus 1.
Să urmărim din nou succesiunea de operaţii pentru acelaşi exemplu (3!), apelăm deci procedura fact cu
valoarea 3 trimisă ca parametru:
(1) apelează recursiv procedura fact, valoarea parametrului este 2;
(2) apelează recursiv procedura fact, valoarea parametrului este 1;
(3) apelează recursiv procedura fact, valoarea parametrului este 0;
(4) returnează 1 în DX:AX – revenire din fact(0);
(5) returnează 1 în DX:AX – revenire din fact(1);
(6) returnează 2 în DX:AX – revenire din fact(2);
(7) returnează 6 în DX:AX – revenire din fact(3);
Procedura afis preia rezultatul din rez (rezultatul se depune în rez înainte de a apela procedura
afis), converteşte această valoare în zecimal şi o afişează.
2. Aplicaţii
1. Modificaţi programul prezentat, înlocuind procedura nerecursivă afis cu o procedură recursivă
Să se realizeze funcţii care rezolvă recursiv următoarele probleme:
2. Calculaţi
⋅ >
=
= −
2 2 , 0
,1 0
2
1
n
n
n
n
3. Calculaţi cel de-al n-lea număr Fibonacci
− + − >
=
=
=
( )1 ( ),2 1
,1 1
,0 0
( )
fibo n fibo n n
n
n
fibo n
4. Calculaţi
+
=
=
=
−
−
− C C in rest
k
n k
C
k
n
k
n
k
n
,
,1 0
,1
1
1
1.
Niciun comentariu:
Trimiteți un comentariu