|
Introducere în recursivitate - Partea I
|
 |
Prezentare generală
Recursivitatea este una dintre noţiunile fundamentale ale informaticii, un mecanism general de elaborare a programelor ce constă în posibilitatea ca un subprogram să se autoapeleze.
Recursivitatea a apărut din necesităţi practice date de transcrierea directă a formulelor matematice recursive. În timp, acest mecanism a fost extins, fiind utilizat în elaborarea multor algoritmi.
Realizarea autoapelului în Logo
În limbajul Logo subprogramele sunt de două feluri: proceduri şi funcţii. Oricare ar fi tipul subprogramului, acesta se poate autoapela, însă modul în care se realizează autotransferul diferă.
a) Proceduri. Procedura prezentată în continuare este recursivă şi afişează, pe rânduri separate, numerele 5, 4, ..., 1.
procedura exemplu :n
daca :n <> 0 [
tipareste :n
exemplu :n-1
]
sfarsit
exemplu 5
b) Funcții. În cazul acestora autoapelul se realizează printr-o operaţie de atribuire, operaţie prin care numele funcţiei trebuie să figureze în partea dreaptă a operatorului de atribuire. Funcţia următoare calculează suma 1+2+...+8:
functie suma :n
var "s 0
daca :n <> 0 [
var "s :n + (suma :n-1)
]
intoarce :s
sfarsit
tipareste suma 8
Observați faptul că, spre deosebire de o procedură, funcția prin instrucțiunea "intoarce" (în engleză, "output") returnează o valoare.
Mecanismul recursivității
Spre exemplu, ne propunem să calculăm n!. Pentru a scrie o funcţie recursivă care efectuează acelaşi calcul, vom porni de la o definiţie recursivă a lui n!. Aceasta este:
3! = fact(3) = 3 x fact(2) = 3 x 2 x fact(1) = 3 x 2 x 1 x fact(0) = 3 x 2 x 1 x 1 = 6
Funcţia recursivă "fact" nu face altceva decât să transcrie definiţia recursivă prezentată anterior:
functie fact :n
var "f 1
daca_altfel :n <> 0
[ var "f :n * (fact :n-1) ]
[ var "f 1 ]
intoarce :f
sfarsit
tipareste fact 5
Cum gândim un algoritm recursiv?
Pentru a ne familiariza cu raţionamentul recursiv, vom porni de la câteva exemple intuitive.
1. O cameră de luat vederi are în obiectiv un televizor care transmite imaginile primite de la cameră. Evident, în televizor se va vedea un televizor, iar în acesta un televizor..., ş.a.m.d. O imagine artistică sugestivă aveți mai jos, care depășește limitele unor dispozitive electronice...
3. Peștișorul de aur îi spune omului că dacă îi dă drumul îi îndeplineşte 3 dorinţe, oricare ar fi ele. Omul îi dă drumul, îi spune prima dorinţă, peştişorul i-o îndeplineşte, îi spune a doua dorinţă, peştişorul i-o îndeplineşte iar. A treia dorinţă este să i se îndeplinească alte 3 dorinţe...
Lăsând gluma la o parte, constatăm că, în general, o gândire recursivă exprimă concentrat o anumită stare, care se repetă la infinit. Această gândire se aplică în elaborarea algoritmilor recursivi, dar cu o modificare esenţială: adăugarea condiţiei de terminare. În absenţa acestei condiţii, nu poate fi vorba de algoritm, întrucât algoritmul trebuie să fie finit.
Observații esențiale
a) În elaborarea algoritmilor recursivi se aplică raţionamentul: "ce se întâmplă la un nivel, se întâmplă la orice nivel".
b) Subprogramul care se autoapelează trebuie să conţină instrucţiunile corespunzătoare unui nivel.
c) Un algoritm recursiv se elaborează utilizând acest tip de gândire, nu o gândire precum cea folosită până acum, când am elaborat algoritmi iterativi.
d) Pentru orice algoritm recursiv există unul iterativ care rezolvă aceeaşi problemă.
e) Nu întotdeauna alegerea unui algoritm recursiv reprezintă un avantaj.
Să privim puțin potențialul...
O frunză...
logo.infobits.ro/view-program.php?user=Vlad-Tudor&program=demo_fern
Un copac...
logo.infobits.ro/view-program.php?user=Vlad-Tudor&program=demo_tree
Un fulg de nea...
logo.infobits.ro/view-program.php?user=Vlad-Tudor&program=Snowflake
Un alt copac (valori aleatorii pe ramuri)...
logo.infobits.ro/view-program.php?user=Vlad-Tudor&program=demo_tree2
În secțiunile următoare veți învăța mai mult despre recursivitate, metoda Divide et Impera și fractali.
