Utilizarea si programarea calculatoarelor - Laborator 5

Recursivitatea

Pentru a evidenţia cele de mai sus, rulaţi următorul program care apelează recursiv funcţia f şi tipăreşte pe parcurs mesaje pentru a indica unde a ajuns execuţia.

#include <stdio.h>

void f(int n)
{
  if (n == 0) return;
  printf("Am intrat în funcţia f cu parametrul %d\n", n);
  f(n - 1);
  printf("Ieşim din funcţia f cu parametrul %d\n", n);
}

int main(void)
{
  f(5);
  return 0;
}

Recursivitatea şi iteraţia

Există o legătură strânsă între recursivitate şi iteraţie; de multe ori,
un program recursiv poate fi transformat foarte uşor într-unul iterativ
şi invers. În ambele cazuri, aceeaşi prelucrare (corpul ciclului, respectiv
al funcţiei recursive) se repetă de mai multe ori. În cazul unui ciclu,
o iteraţie modifică valorile unor variabile, şi iteraţia următoare se
execută pentru valorile noi; la fel, apelul recursiv se face în general
cu alte valori ale parametrilor faţă de cele iniţiale.  În ambele cazuri,
pentru un algoritm corect, prelucrarea trebuie să se încheie după un număr
finit de paşi: acest lucru e asigurat de condiţia de ieşire din ciclu,
respectiv de cazul de bază al recursivităţii, în care funcţia returnează
direct o valoare, fără a se mai apela recursiv.

Un exemplu simplu prezentat la curs e cel al tipăririi unui şir:
void puts_nonrec(char *s)
{
  while (*s) {		/* condiţia de oprire: *s = '\0' */
    putchar(*s);	/* prelucrarea: tiparirea unui caracter */
    s = s+1;		/* variabila modificata: s (incrementat) */
  }
  putchar('\n');	/* cazul de baza: la ieşirea din iteraţie */
}
void puts_rec(char *s)
{
  if (*s) {		/* condiţia de oprire: *s = '\0' */
    putchar(*s);	/* prelucrarea: tiparirea unui caracter */
    puts_rec(s+1);		/* noul parametru de apel: s+1 in loc de s */
  } else putchar('\n'); /* cazul de baza: la ieşirea din recursivitate */
}

Un alt exemplu este cel al cautarii binare al unei valori v
într-un tablou a, între indicii l şi r inclusiv.
double *bsearch_nonrec(double v, double *a, int l, int r) {
  while (l < r) {	/* cât timp intervalul are >= 2 elemente */
    int m = (l+r)/2;	/* calculează punctul de mijloc */
    if (v>a[m]) l = m+1;/* continuă căutarea în intervalul din dreapta */
    else r = m;		/* continuă căutarea în intervalul din stânga */
  }			/* iese când intervalul e degenerat, <= 1 element */
  if (v==a[l]) return a+l;	/* returnează adresa elementului gasit */
  else return NULL;		/* sau NULL dacă elementul nu a fost găsit */
}
double *bsearch_rec(double v, double *a, int l, int r) {
  int m = (l+r)/2;
  if (l < r) {		/* continuă recursivitatea dacă >= 2 elemente */
    if (v>a[m])		/* continuă căutarea în intervalul din dreapta */
      return bsearch_rec(v, a, m+1, r);	/* cu noul parametru l egal cu m + 1 */
    else		/* continuă căutarea în intervalul din stânga */
      return bsearch_rec(v, a, l, m);	/* cu noul parametru r egal cu m */
  } else		/* iese din recursivitate pentru interval <= 1 */
    if (v==a[l]) return a+l;	/* returnează adresa elementului gasit */
    else return NULL;		/* sau NULL dacă elementul nu a fost găsit */
}


De cele mai multe ori, varianta iterativă a unui algoritm e mai performantă
decât cea recursivă, pentru că evită costul suplimentar al apelurilor de
funcţie, împreună cu salvarea pe stivă şi transmiterea parametrilor.
Mai mult, în cazul unei adâncimi excesive a recursivităţii, se poate
produce depăşirea stivei.  Sunt însă multe cazuri în care recursivitatea e
modalitatea naturală de rezolvare, şi alte soluţii ar fi sensibil mai
complicat şi neintuitiv de exprimat.

Problemă: Funcţia putere
Scrieţi o versiune recursivă pentru funcţia putere cu bază reală şi exponent
întreg, bazată pe definiţia recursivă:
x la puterea n = x * x la puterea (n - 1)
pentru n > 0.  Completaţi apoi funcţia şi pentru exponent negativ.

Problemă: Inversarea unui şir
Scrieţi un program care citesţe de la intrare o linie de text şi o afişează
în ordine inversă (de la coadă la cap).  Folosiţi o funcţie recursivă.

Şi în acest caz, programul se poate obţine direct din formularea recursivă
mai întâi a structurii de date care trebuie prelucrată, şi apoi a prelucrării:

- o linie de text este o linie vidă (caracterul '\n') sau
un caracter urmat de o linie de text

- dacă linia e formată din caracterulc şi restul r,
inversa ei e formată din inversa lui r urmată de c.

Se observă că efectul unei funcţii recursive depinde în mod critic de
locul unde e plasat apelul recursiv în cadrul prelucrării din corpul
funcţiei (la început, la mijloc sau la sfârşit).

Ca alternativă, scrieţi o variantă recursivă pentru funcţia strrev
care ia ca parametru un şir de caractere şi returnează, alocat dinamic,
inversul lui (de la coadă la cap).

Problemă: Rezolvarea unei ecuaţii prin metoda înjumătăţirii

În semestrul trecut, aţi implementat la laborator găsirea rădăcinii unei
funcţii continue şi monotone pe un interval, cu o precizie dată, dacă
funcţia are semne diferite la capetele intervalului. Se calculează valoarea
funcţiei la mijlocul intervalului şi se continuă căutarea in acea jumătate
de interval pe care funcţia schimbă semnul. Implementaţi recursiv algoritmul
descris mai sus.

Problemă: Minimul/maximul unui şir
Scrieţi o funcţie recursivă care ia ca parametri un tablou de numere şi
respectiv lungimea lui şi returnează valoarea numărului minim din tablou.
Pentru un tablou de lungime n > 1 se află întâi minimul primelor
n - 1 elemente, şi apoi se ia minimul dintre această valoare şi
ultimul element.

Problemă: Sortarea unui tablou

Sortarea prin selecţie şi cea prin metoda bubblesort au în comun faptul că
după prima iteraţie exterioară, elementul extrem al tabloului (minim sau maxim,
în funcţie de sensul ales) este poziţionat corect la capăt, după care procedura
se reia pentru al doilea element în mărime, etc. Folosind una din metode,
implementaţi recursiv procedura de sortare, dându-i ca parametri tabloul şi
lungimea lui. Poziţionaţi corect ultimul (cel mai mare) element, după care
apelaţi recursiv pentru restul tabloului (de la începutul său, dar de lungime
cu 1 mai mică).

Problemă: Şiruri binare de lungime dată
Scrieţi un program care tipăreşte în ordine lexicografică (alfabetică)
toate şirurile de lungime dată N formate din cifrele 0 şi 1.
Folosiţi o funcţie recursivă care pune pe rând 0 şi respectiv 1 pe poziţia
următoare în şir, iar dacă a ajuns la sfârşit tipăreşte şirul.


În acest caz, vor exista două apeluri recursive ale funcţiei în corpul său,
iar numărul total de apeluri e exponenţial (ca şi numărul de şiruri distincte,
2 la puterea n).

    

    
Marius Minea


Last modified: Mon Mar 22 08:27:50 EET 2004