Recursivitate

Problema recursivitatii mi s-a parut una dintre cele mai interesante subiecte din programare. In ce consta? In apelarea ei insasi a unei functii sau proceduri. De exemplu, ceva de genul:


Private Sub o_procedura()
...
if o_conditie then call o_procedura
...
End Sub

De fapt, asta este solutia si pentru cea mai interesanta problema de programare, evident dupa parerea mea, si anume problema turnurilor din Hanoi:
"Se dau 3 pozitii pe care se pot muta un numar n de discuri de diametre diferite aranjate crescator in ordinea diametrelor, initial aflate pe una din pozitii. Problema consta in a muta toate aceste discuri de pe o pozitie pe alta folosind a treia pozitie cu conditia ca in ORICE moment sa nu existe un disc de diametru mai mare peste unul de diametru mai mic (tot timpul sa fie ordonate)"
Inainte de asta insa sa vedem alte exemple de utilizare a acestei metode.

De exemplu, ne propunem sa calculam factorialul unui numar n. Sa presupumen ca avem o astfel de functie, atunci o folosim ca mai jos (avem un buton de comanda si un text-box pe forma care contine numarul caruia ii calculam factorialul):


Private Sub cmdFactorial_Click()
Cls
Print Factorial1(txtFactorial)
End Sub

Sa vedem codul unei astfel de functii:


Dim rez As Long

Private Function Factorial1(ByVal n As Integer) As Long
If n = 1 Then
    rez = 1
Else
    Factorial1(n - 1)
    rez = rez * n
End If
Factorial1 = rez
End Function

       Ce se intimpla de fapt? Mai intii se apeleaza functia Factorial1 de n ori (fara a ajunge la rez = rez * n). Cind n este 1, initializam rezultatul (rez) si se revine de n ori din functia care s-a autoapelat, executindu-se de n ori rez = rez * n (intre apelurile succesive ale functiei, n este pastrat pe stiva, la terminarea executarii functiei o data se revine la valoarea anterioara a lui n, luata din stiva interna). Se intimpla asa pentru ca Visual Basicul salveaza in stiva variabilele globale sau locale la apelarea unei functii sau proceduri, iar la terminarea functiei sau procedurii apelate se revine la vechile valori. Observati ca valoarea n am dat-o ca parametru transmis prin valoare si nu ca referinta (daca folosim ByVal transmitem valoarea nu referinta variabilei) desi se putea transmite si referinta variabilei.
       In aceasta functie am folosit o variabila globala (rez), care in general poate fi o solutie ocolita de multa lume.
       Alta solutie pentru aceeasi problema fara utilizarea unei variabile globale (in forma) este urmatoarea:


Private Function Factorial2(ByVal n As Integer) As Long
Static x As Long
If n = 1 Then
    x = 1
Else
    Factorial2 (n - 1)
    x = x * n
End If
Factorial2 = x
End Function

Aceasta solutie nu difera prea mult fata de cea anterioara cu mentiunea ca s-a inlocuit variabila globala rez cu o variabila locala statica (x) care nu este vizibila din afara functiei.
In sfirsit sa prezentam si a treia solutie in care nu se mai foloseste nici o variabila suplimentara si returneaza direct rezultatul. Evident este cea mai eleganta solutie.


Private Function Factorial3(ByVal n As Integer) As Long
If n = 1 Then
    Factorial3 = 1
Else
    Factorial3 = Factorial3(n - 1) * n
End If
End Function

Mai intii se autoapeleaza functia Factorial3 de n ori, iar apoi la revenirea din fiecare apel se calculeaza factorialul direct ca rezultat de returnat.
Va intrebati, poate, de ce nu se poate scrie si mai simplu ceva de genul:


Private Function Factorial4(ByVal n As Integer) As Long
Factorial4 = IIf(n = 1, 1, Factorial4(n - 1) * n)
End Function

Asta nu merge pentru simplul motiv ca indiferent de conditia din IIf se evalueaza atit partea true cit si partea pt. false. Asta inseamna ca indiferent de valoarea lui n functia se autoapeleaza. Nu ar trebui sa se autoapeleze decit pentru n > 1.

Alta problema care se poate rezolva folosind recursivitatea este generarea tuturor permutarilor unei multimi. De fapt, problema se reduce la permutarea numerelor de la 1 la n care reprezinta valorile indicilor sirului (multimii) de permutat. Sa vedem mai intii cum se poate folosi o astfel de procedura (am pus pe forma un buton si un text-box care contine numarul de elemente al multimii - de la 1 la max).


Dim a() As Integer
Dim max As Integer

Private Sub cmdPermutari_Click()
max = txtPermutari
ReDim a(max)
Cls
Call Permutari(1)
End Sub

Procedura ar putea fi urmatoarea:


Private Sub Permutari(ByVal n As Integer)
Dim i As Integer
Dim j As Integer
Dim b As Boolean
For i = 1 To max
a(n) = i
    b = False
    For j = 1 To n - 1
    If a(j) = i Then b = True
    Next
    If Not b Then
        If n = max Then
            For j = 1 To max
            Print a(j);
            Next
            Print
        Else
            Call Permutari(n + 1)
        End If
    End If
Next
End Sub

Si aici folosim variabile globale max si a desi max ar putea fi transmis ca parametru, iar sirul a ar putea fi declarat static in functie.
De fapt, se folosesc atitea cicluri for..next cite autoapeluri a procedurii avem (de max ori). Astfel, pentru fiecare element de la 1 la max avem cite un ciclu for..next cu valori de la 1 la max. Pentru fiecare valoarea care trebuie pusa pe o pozitie in sirul a se face o verificare daca nu a mai fost pusa deja. Daca a mai fost pusa anterior, b = True si trece la urmatoarea valoare pentru aceeasi pozitie. Cind se ajunge la ultima pozitie se face afisarea sirului direct pe forma. Daca nu s-a ajuns la ultima pozitie, se autoapeleaza procedura pentru a creea inca un ciclu for..next si pentru aceasta pozitie.

Aproape la fel este procedura pentru calcul aranjamentelor (de max luate cite m) folosita ca mai jos (am pus pe o forma un buton si 2 text-box-uri care contin numarul de elemente si cite elemente se iau in aranjament):


Dim a() As Integer
Dim max As Integer
Dim m As Integer

Private Sub cmdAranjamente_Click()
max = txtAranjamente1
m = txtAranjamente2
ReDim a(m)
Cls
Call Aranjamente(1)
End Sub

Aranjamentele se pot calcula astfel:


Private Sub Aranjamente(ByVal n As Integer)
Dim i As Integer
Dim j As Integer
Dim b As Boolean
For i = 1 To max
a(n) = i
    b = False
    For j = 1 To n - 1
    If a(j) = i Then b = True
    Next
    If Not b Then
        If n = m Then
            For j = 1 To m
            Print a(j);
            Next
            Print
        Else
            Call Aranjamente(n + 1)
        End If
    End If
Next
End Sub

Ce se schimba fata de procedura pentru calculul permutarilor? Nu prea mult. Se schimba doar pozitia de sfirsit, adica locul unde se afiseaza rezultatul. Daca la permutari mergeam pina la capatul sirului (aveam max cicluri for..next) la aranjamente avem doar m cicluri for..next (m <= max).

Dupa acelasi model se pot genera si combinatiile de max luate cite m ca mai jos (am pus un buton si 2 text-box-uri pe forma):


Dim a() As Integer
Dim max As Integer
Dim m As Integer

Private Sub cmdCombinari_Click()
max = txtCombinari1
m = txtCombinari2
ReDim a(m)
Cls
Call Combinari(1)
End Sub

Procedura pentru calculul efectiv al combinarilor este urmatoarea:


Private Sub Combinari(ByVal n As Integer)
Dim i As Integer
Dim j As Integer
Dim b As Boolean
For i = 1 To max
a(n) = i
    b = False
    For j = 1 To n - 1
    If a(j) >= i Then b = True
    Next
    If Not b Then
        If n = m Then
            For j = 1 To m
            Print a(j);
            Next
            Print
        Else
            Call Combinari(n + 1)
        End If
    End If
Next
End Sub

Diferenta fata de aranjamente este un singur semn in plus (>). Daca la aranjamente se iau toate posibilitatile de aranjare a max elemente luate cite m, la combinatii pentru a nu avea dubluri de siruri (exemplu 1, 2, 3 si 3, 2, 1) pastram tot timpul sirul a ordonat crescator. De aceea, If a(j) = i Then b = True s-a transformat in If a(j) >= i Then b = True.

Si acum sa revenim la problema initiala. Mai intii sa vedem sursa programului dupa care o vom analiza. Punem pe o forma un buton si un text-box care contine numarul de discuri. Presupumen ca mutam discurile de pe prima pozitie pa a 2-a folosind a 3-a pozitie. Apoi scriem:


Private Sub cmdHanoi_Click()
Cls
Call Hanoi(txtHanoi, 1, 2, 3)
End Sub

Private Sub Hanoi(ByVal n As Integer, _
	ByVal a As Integer, ByVal b As Integer, ByVal c As Integer)
If n > 0 Then
    Hanoi n - 1, a, c, b
    Print "Pune de pe " & a & " pe " & b
    Hanoi n - 1, c, b, a
End If
End Sub

Pare simplu, nu-i asa? Cine intelege ce se intimpla de fapt, aici, intelege in ce consta recursivitatea, dupa parerea mea.
Mai intii se muta n-1 discuri de pe pozitia 1 (a) pe 3 (c), apoi se muta un singur disc de pe pozitia 1 (a) pe pozitia 2 (b), iar in final se muta n-1 discuri de pe pozitia 3 (c) pe pozitia 2 (b). Cum se muta n-1 discuri de pe o pozitie pe alta? Prin utilizarea aceleasi proceduri (prin autoapelarea procedurii). Cel mai bun sfat este sa executati procedura pas cu pas (cu F8) si sa urmariti valorile parametrilor.

Observatii:

De transformarea textului din text-box-uri in valori integer transmise procedurilor sau functiilor se ocupa Visual Basicul, singur.
Nu am dat prea mare atentie afisarii rezultatelor. Le-am pus direct pe forma desi s-ar putea nu incapa si deci sa nu vedeti toate valorile.

Propuneri:

Scrieti o procedura pentru generarea permutarilor care nu foloseste recursivitatea.
Problema damelor: Aranjati pe o tabla de n x n, n dame care sa nu se atace, folosind recursivitatea.