Enrere Mòdul 4
Fonaments de Programació. Llenguatge C/C++---
Pràctica  Exercicis
Pràctica d'ampliació Annex: la depuració

 

Resum Teòric


La recursivitat

Sempre s'ha dit que la paraula a definir no pot estar en la definició. No obstant això, aquesta regla no és certa en molts llenguatges de programació com ara el C/C++. Un llenguatge de programació es diu que és recursiu si una funció (o subprograma) pot cridar-se a sí mateixa.

Un algorisme recursiu és una altra forma de fer repeticions sense emprar estructures iteratives com while, do...while o for.

Per tal que un algorisme recursiu no s'executi indefinidament, és sempre necessari que hi hagi un cas (en general el més simple) totalment definit i que no necessita cridar de nou a la funció.

La major part dels algorismes recursius admeten també una estructura iterativa. Habitualment, el codi iteratiu és més ràpid que el codi recursiu, a més, si la crida a la funció es fa moltes vegades, com que cada vegada l'ordinador ha de guardar espai de memòria per a les variables de cada crida, és fàcil que es desbordi aquesta memòria (la memòria destinada a les variables locals i paràmetres de la funció s'anomena pila).

Un exemple típic de funció que es pot escriure de forma recursiva és la funció factorial. Es defineix el factorial d'un nombre enter positiu n (i notarem n!) com el producte de tots els números enters positius més petits o igual a n, és a dir: n!=n·(n-1)·(n-2)·...2·1. A continuació es presenta dues formes d'implementar la funció factorial, una iterativa amb la sentència for i una altra recursiva, la funció recursiva es basa en el fet que n!=n·(n-1)!:

int factorial(int n){             //versió iterativa
      int i=1, f=1;
      for(i=1;i<=n;i++) f=f*i
      return(f);
}

 

int factorial(int n){            //versió recursiva
      if(n==0)return 1;
      return(n*factorial(n-1));
}

L'exemple anterior és un cas de recursivitat simple, és a dir, un cas en el qual en el cos de la funció només apareix una crida a sí mateixa. Una mostra de recursivitat múltiple, és a dir que en el cos de la funció apareixen més d'una crida a sí mateixa la tenim en el següent exemple que calcula el terme n-ésim de la successió de Fibonacci. Aquesta successió es defineix de la següent forma: 

a1=1                 a2=2                      an=an-1+an-2      si n>2

Els primers termes de la successió de Fibonacci són: {1,2,3,5,8,13,21,...}

El codi per implementar aquesta successió és:

int fibon(int n){
     if(n<=1) return 1;
     return(fibon(n-1)+fibon(n-2));
}

Per últim, també es pot fer una recursivitat indirecta, és a dir, que la funció no es cridi directament a sí mateixa, sinó que la funció cridi a una segona funció  i aquesta segona cridi a la funció inicial, per exemple, aquestes dues funcions es criden l'una a l'altra, ambdues funcions tornen 1 si el seu argument és el que indica el nom de la funció i 0 en altre cas:

int parell(int n){
     if(n==0) return 1;
     return senar(n-1);
}

int senar(int n){
     if(n==0) return 0;
     return parell(n-1);
}

 

Els nombres pseudoaleatoris

Com gairebé tots els llenguatges de programació, C incorpora en la seva llibreria estàndard una funció que genera un nombre pseudoaleatori. En el cas concret del C, aquest nombre és un enter comprès entre 0 i 32.767. El prototipus d'aquesta funció és:

int rand()

i per tal de fer-la servir s'ha d'incloure el fitxer de capçalera stdlib.h.

Altres llenguatges de programació incorporen també una funció similar. Normalment és una funció que genera un nombre real de l'interval [0, 1). Aquesta funció és més útil en molts casos.

Per tal de generar en C un nombre real entre 0 i 1 (incloent el 0 i excloent l'1) podem fer servir l'expressió:

(float) rand()/32768

Per tal de generar un nombre real entre 0 i n ( [0,n) ) es fa servir l'expressió:

(float) rand()*n/32768

De fet, aquesta expressió, com l'anterior, generarà un nombre real d'entre 32768 nombres reals compresos entre 0 i n, no seguirà estrictament, per tant, una distribució uniforme.

Per tal de generar un nombre enter entre 0 i n–1, ambdós inclosos i n<32768, es fa servir l'expressió:

rand()*n /32768

Si n>32768 aquest mètode farà que hi hagi nombres que no es generaran, per exemple, si n/32768 = 2, tots els nombres generats seran parells. Aquest problema es pot solucionar generant dos números aleatoris, per exemple:

rand()*32768+rand()

és un nombre aleatori comprès entre 0 i 1.073.741.824

L'algorisme intern que utilitza la funció rand() fa servir una llavor o valor inicial per iniciar la seqüència de nombres aleatoris. La funció srand() permet assignar un valor nou a aquesta llavor o valor inicial.

--- ---