Cum gândim un algoritm recursiv? – exemple

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 limbajul 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:

De exemplu, pentru a calcula 3!, procedăm astfel:

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

Simplu, nu? Sunt doar 8 linii de cod.

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…

* Interesant acest efect, având în vedere că poartă numele producătorului olandez de cacao ce a folosit prima oară tehnica aplicată de Jan Musset în anul 1904:

2. În anumite restaurante întâlnim anunţul: “Azi nu se fumează!“. Și mâine e o zi, nu?

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 …
Executați programele de mai jos pentru a vizualiza animațiile:

1. Un copac cu ramuri aleatorii
https://logo.infobits.ro/view-program.php?user=Vlad-Tudor&program=demo_tree2

2. Un fulg de nea
https://logo.infobits.ro/view-program.php?user=Vlad-Tudor&program=Snowflake

3. O frunză complexă
https://logo.infobits.ro/view-program.php?user=Vlad-Tudor&program=demo_fern

Recursivitatea este minunată, iar programele au câteva linii de cod în mod grafic interactiv pe [logo.infobits.ro]. Platforma online este creată cu ajutorul limbajului JavaScript, pe un element de tip canvas, iar forța de calcul la nivel de animație este uimitoare.

Platforma globală de programare în Logo poate fi găsită la adresa [logointerpreter.com], unde sunt programe distribuite de elevi și profesori de pe toate continentele. În cadrul acelui proiect, programarea este efectuată exclusiv în limba engleză, cu instrucțiunile corespunzătoare. Mai multe detalii găsiți pe site.

Surf Your Logo Code!