Índex
 
Capítol 11 Exercicis
Capítol 11

La recursivitat

  1. Concepte de recursivitat
  2. La recursivitat indirecta
  3. L'algorisme recursiu OrdenaRapido (quick sort).
    1. La instrucció qsort del C.
  4. Un arbre recursiu
  5. Comentari final
  6. Exercicis

 

11.1. Concepte de recursivitat

Una funció es diu recursiva si s'executa a si mateixa. El primer exemple de funció recursiva es el seguent:
 
void Castig(void) 
{
    printf("Aixó és un càstig infinit"); 

    Castig();
} 

Aquesta funció es crida a si mateixa. Cada vegada que es crida crea una instància nova en memòria de la funció.

Com que no té cap instrucció de sortida no para de cridar-se a si mateixa i de crear instàncies de si mateixa. El programa peta quan s'omple la memòria de funcions en execució (pila del programa). És un exemple d'allò que no hem de fer mai amb funcions recursives.

Les funcions recursives poden rebre i tornar paràmetres com qualsevol altra funció.

Normalment es fa ús d'un paràmetre per controlar, entre d'altres coses, quan a de aturar-se de cridar-se a sí mateixa

La funció següent escriu en pantalla números naturals de manera decreixent. La funció para de cridar-se a si mateixa quan el valor de Numero es igual a zero:
 

#include <stdio.h>

void CuentaAlReves(int Numero);

main()
{
    CuentaAlReves(10);
}

void CuentaAlReves (int Numero)
{
    printf("%d\n",Numero); 

    if (Numero >0) CuentaAlReves(Numero-1);
}

Observem en la figura quin és el flux d'execució i creació simultània de funcions CuentaAlReves.

És fa notar que cada crida recursiva fa que s'executi una nova instància de la funció diferent de les altres, de manera que cadascuna d'elles manté actives les seves pròpies variables.

També és curiós observar que les instruccions de FIN de funció s'executen al contrari de com tendeix un a pensar que haurien d'executar-se.

La funció EscribeNumeros es quasi igual que la funció anterior, però els números s'escriuen en ordre creixent:
 

#include <stdio.h>

void EscribeNumeros(int Num);
main()
{
    EscribeNumeros(10);
}

void EscribeNumeros(int Num)
{
    if (Num > 0) EscribeNumeros(Num-1);
    printf("%d\n",Num);
} 

Si observem que la crida recursiva es fa abans que s'executi la instrucció d'escriure entendrem perquè ara els números s'escriuen en ordre creixent.

Allò que no s'ha de fer: si una situació no és recursiva no s'ha d'utilitzar la recursivitat per a programar-la. Cap dels programes anteriors correspon a situacions realment recursives, si no a situacions merament repetitives. No s'haurien d'haver escrit així.

Allò que si s'ha de fer: El factorial d'un número n es n! = n(n-1)(n-2)x....x3x2x1. Aquesta forma de definir-lo no és recursiva. Però també pot definir-se en la manera n! = n(n-1)! i aquesta forma si que és recursiva. Es pot escriure la funció recursiva següent.
 

#include <stdio.h>

long double Factorial(int Num);

main()
{
    int Num; 

    printf("Escribe un número entero positivo ");
    scanf("%d",&Num);
    if (Num>0) printf("Su Factorial es %Lf\n", Factorial(Num));
    else printf("Solo números positivos");
}

long double Factorial(int Num) 
{
    long double Fact=1;

    if (Num>1) Fact=Num*Factorial(Num-1);

    return Fact;
} 

És convenient que com exercici facis el diagrama de flux d'execució d'aquesta funció amb una crida Factorial(5).

11.2. LA RECURSIVITAT INDIRECTA

Joc de les torres de Hanoi

Es disposa d'una torre com la de la figura esquerra, de qualsevol número de peces, i de tres posicions, esquerra, mig i dreta. El joc consisteix en pasar la torre d'una posició a una altra movent una peça cada vegada, però amb la condició de que no es poden col·locar peces més petites a sota de peces més grans.

Farem ara l'explicació del l'algoritme recursiu que realitza el joc de les torres:
 

Torre d'una peça Torre a la dreta (d'una peça).
Torre de dues peces Torre a la dreta (d'una peça).
Peça de l'esquerra al mig.
Torre a l'esquerra (d'una peça).
Peça del mig a la dreta.
Torre a la dreta (d'una peça).
Torre de tres peces Torre a la dreta (de dues peces).
Peça de l'esquerra al mig.
Torre a l'esquerra (de dues peces).
Peça del mig a la dreta.
Torre a la dreta (de dues peces).
Torre de quatres peces Torre a la dreta (de tres peces).
Peça de l'esquerra al mig.
Torre a l'esquerra (de tres peces).
Peça del mig a la dreta.
Torre a la dreta (de tres peces).

Aquests passos es poden seguir indefinidament i passar qualsevol número de peces d'un costat a un altre. En el joc, i per a una torre de n peces es realitzen cinc tipus de moviment. Tres moviments corresponen a una crida al joc d'una torre de n-1 peces, un moviment a la esquerra i dos moviments a la dreta. Així el programa que realitza aquest joc és el següent:
 

#include <STDIO.H>

void HanoiEsquerra(int peces);
void HanoiDreta(int peces);

main()
{
    HanoiDreta(3);
}

void HanoiDreta(int peces)
{
    if (peces==1) printf("peça de l'esquerra a la dreta\n");
    else
    {
       HanoiDreta(peces-1);
       printf("Peça de la esquerra al mig\n");
       fflush(stdin);getchar();
       HanoiEsquerra(peces-1);
       printf("Peça del mig a la dreta\n");
       fflush(stdin);getchar();
       HanoiDreta(peces-1);
    }
}

void HanoiEsquerra(int peces)
{
    if (peces==1) printf("peça de la dreta a l'esquerra\n");
    else
    {
       HanoiEsquerra(peces-1);
       printf("Peça de la dreta al mig\n");
       fflush(stdin);getchar();
       HanoiDreta(peces-1);
       printf("Peça del mig a l'esquerra\n");
       fflush(stdin);getchar();
       HanoiEsquerra(peces-1);
    }
} 

11.3. L'algorisme recursiu OrdenaRapido (quick sort).

Aquest mètode de ordenació és un dels més ràpids que existeixen. Per a estudiar-ho primer analitzarem la porció de programa que fa particions d'un vector o clau en dos subvectors que volem ordenar.

Suposem que tenim un vector que volem ordenar i que la primera posició és Esquerra i la última és Dreta.

Es tracta de dividir els valors que tenim entre Esquerra i Dreta en dos blocs de manera que tots els nombres del primer bloc siguin més petits que els del segon bloc.

S'agafa el valor que es troba al mig, entre Esquerra i Dreta i cerquem:
 

  1. el primer valor dels que tenim a l'esquerra de x que sigui més gran que x. (Si existeix)
  2. el primer valor dels que tenim a la dreta de x que sigui més petits que x. (Si existeix)
Intercanviem els valors d'aquestes dues posicions i seguim cercant valors que tinguin aquesta condició fins que trobem la x.
 
x=a[(int)((float)(Esquerra+Dreta) / 2)];
do 
{
    while (a[i] < x) i = i + 1;
    while (a[j] > x) j = j - 1;
    if (i<=j) 
    {
       w = a[i]; a[i] = a[j]; a[j]= w;
       i = i + 1; j = j - 1;
    }
} while (i<=j); 

Bé, els valors finals per a els índex són i = 5 y j =3. Així ja tenim el vector dividit en dues parts. Tots els elements de la primera part són més petits que els de la segona. Podem seguir dividint la primera part en dues i la segona també i així succesivament fins que el vector estigui ordenat.

D'aquesta manera podem plantejar la funció recursiva següent que fa diverses crides recursives segons el número d'elements del vector.
 
 

#include <stdio.h>

void OrdenaRapido(int Esquerra,int Dreta, int vecrtor[]);

main()
{
    int i; 

    int vectorAOrdenar[10]= {0,1,3,9,4,2,-2,-3,-4,10};
    OrdenaRapido(0,9, vectorAOrdenar);
    for (i=0;i<10;i++) printf("%2d\n",vectorAOrdenar[i]);

    return 0;
}

void OrdenaRapido(int Esquerra,int Dreta, int vector[])
{
    int i,j,x,w;

    i=Esquerra; j=Dreta;
    x= vector[(int)((float)(Esquerra+Dreta) / 2)];
    do
    {
       while (vector[i] < x) i = i + 1;
       while (vector[j] > x) j = j - 1;
       if (i<=j)
       {
          w = vector[i]; vector[i] = vector[j]; vector[j]= w;
          i = i + 1; j = j - 1;
       }
    }while (i<=j);
    if (Esquerra < j) OrdenaRapido(Esquerra, j,vector);
    if (i < Dreta) OrdenaRapido(i,Dreta,vector);
}

11.3.1 La instrucció qsort del C.

Per explicar la funció qshort del C tenim un programa amb una base de dades. Observa la capçalera del programa que inclou els arxius conio.h i subru.h. Es defineix l'estructura de la base de dades i s'anomena Cicle. Es declara una matriu de 16 registres de M3PI de tipus Cicle i es dona valor als camps Nom, Assigs i Adreca dels setze registres. 
#include <conio.h>
#include <subru.h>

struct Cicle {
                char Nom[46];
                char Assigs[45];
                char Adreca[35];
                char Telefon[10];
                char NotaMetodologia[4];
                char NotadBase[4];
} M3PI[16]={
        {"GONZALEZ,GOMEZ;ELVIRA","M3METM3PRCM3ANGM3INBM3DBSM3TEXM3LAB","SABADELL s/n"},
        {"CUEVAS,SORIANO;JESUS","M3METM3PRCM3ANGM3INBM3DBSM3TEXM3LAB","BARCELONA 127"},
        {"ALVAREZ,CANTERO;FCO. JOSE","M3METM3PRCM3ANGM3INBM3DBSM3TEXM3LAB","TERRASSA 34"},
        {"TORRES,ANTON;GINES","M3METM3PRCM3ANGM3INBM3DBSM3TEXM3LAB","TAMARIT 23"},
        {"COBO,SANCHEZ;ANTONIO","M3METM3PRCM3ANGM3INBM3DBSM3TEXM3LAB","SOCIAS 56"},
        {"SANCHEZ,EMBID;JUAN ANTONIO","M3METM3PRCM3ANGM3INBM3DBSM3TEXM3LAB","BARBERA 3"},
        {"CABALLE,COSTA;ESTEL","M3METM3PRCM3ANGM3INBM3DBSM3TEXM3LAB","STA TERPETUA 12"},
        {"ADRIAN,ESCUDERO;SARA","M3METM3PRCM3ANGM3INBM3DBSM3TEXM3LAB","LUMBRERES 35"},
        {"ALEPUZ,MASO;ALEJANDRO","M3METM3PRCM3ANGM3INBM3DBSM3TEXM3LAB","CANDELES 15"},
        {"ALEPUZ,MASO;JAVIER","M3METM3PRCM3ANGM3INBM3DBSM3TEXM3LAB","CARBONERS 17"},
        {"UCEDA,MADIALDEA;M¦ ANTONIA","M3METM3PRCM3ANGM3INBM3DBSM3TEXM3LAB","PANADERS 19"},
        {"GONZALEZ,CASTILLO;RAMONF.","M3METM3PRCM3ANGM3INBM3DBSM3TEXM3LAB","TALABARDERS 123"},
        {"BONILLA,BERNAL;SILVIA","M3METM3PRCM3ANGM3INBM3DBSM3TEXM3LAB","QUINCALLERS 12"},
        {"ANGELET,GIMENO;JAVIER","M3METM3PRCM3ANGM3INBM3DBSM3TEXM3LAB","PEIXETERS 11"},
        {"POLO,VILLATORO;MANUEL","M3METM3PRCM3ANGM3INBM3DBSM3TEXM3LAB","PELOTARIS 34"},
        {"LUNA,PEREZ,JUAN DIEGO","M3METM3PRCM3ANGM3INBM3DBSM3TEXM3LAB","TAMVIAIRES 128"}
};
En la capçalera tenim declarades tres funcions:
  1. La funció Imprimeix que escriu a la pantalla les dades Nom i Adreca de tots els registres.
  2. La funció OrdreNoms en la que s'indica a la funció qshort la clau d'ordenació per noms.
  3. La funció OrdreAdreca en la que s'indica a la funció qshort la clau d'ordenació per adreces.
void Imprimeix(void);
int OrdreNoms(const void *a, const void *b);
int OrdreAdreca(const void  *a,const void *b);

La funció principal s'encarrega de imprimir i ordenar els registres

int main(void) {
        Imprimeix();
        qsort( (void *)M3PI, 16, sizeof(M3PI[0]),OrdreNoms);
        Imprimeix();
        qsort( (void *)M3PI, 16, sizeof(M3PI[0]),OrdreAdreca);
        Imprimeix();
        return 0;
}
Per últim tenim les tres funcions:

void Imprimeix(void) {
        int i;
        char Eti1[45]="Nom";
        char Eti2[45]="Adreça";
        clrscr();
        cprintf("LLISTA DE DADES\r\n\n");
        cprintf("Re %-40s %-35s\r\n\n",Eti1,Eti2);
        for(i=0;i<16;i++)
                cprintf("%2d %-40s %-35s\r\n",i,M3PI[i].Nom,M3PI[i].Adreca);
        EsperaTecla(0);
}

int OrdreNoms(const void *a, const void *b){
        return(strcmp((char *)a, (char *)b));
}

int OrdreAdreca(const void *a, const void *b){
        return(strcmp((char *)a+91, (char *)b+91));
}
La funció qsort està definida en la forma següent:
  
void qsort(void *base, size_t nelem, size_t amplada, int (*fcmp)(const void *, const void *);
Aquesta funció inclou 4 paràmetres:
 
  1. base es un punter a l'element 0 dels items a ordenar, en el nostre cas és M3PI.
  2. nelem és el número de items a ordenar, en el nostre cas 16.
  3. amplada és la mida en bytes dels items a ordenar.
  4. *fcmp és una funció que hem d'escriure nosaltres i que rep dos paràmetres. Els dos paràmetres que rep la funció son dos punters l'un al byte 0 d'un dels items a ordenar i l'altre és un altre punter que apunta a un altre item. La funció ha de retornar
    1. un valor negatiu si el primer item és posterior al segon
    2. un número zero si els dos items son iguals
    3. un valor positiu si el primer item és anterior al segon
Els punters que rep aquesta funció apunten en el nostre cas al primer caràcter dels registres, per tant al primer caràcter dels noms. Així la funció OrdreNoms fa el següent retorn: 
         return(strcmp((char *)a, (char *)b));
Si volem ordenar per un altre camp hem de desplaçar el punter tants llocs com sigui necessari, així si volen ordenar per adreces hem de fer el següent retorn: 
         return(strcmp((char *)a+91, (char *)b+91));
Si comptes veuràs que totes les adreces comencen al lloc 91.

11.4. Un arbre recursiu

Mira l'arbre de la figura:

Per a dibuixar les dues primeres branques amb un llapis que no es lleva del paper haurem de realitzar els següents moviments:
  

        Gira a la Esquerra 45
        Avança longitud de rama
        Recula longitud de rama
        Gira a la Dreta 90
        Avança longitud de rama
        Recula longitud de rama
        Gira a la Esquerra 45
Però després d'haver dibuixat la primera branca haurem de dibuixar un arbre en el que les primeres branques tenen la meitat de longitud. Es a dir que hem de fer unes crides de tipus recursius per a dibuixar totes les branques i en tota la seva profunditat.

Un algoritme que dibuixa aquest arbre és el següent:
 
 
 

Procediment Arbre(Longitud de rama)
    Si rama > 2
        Gira a la Esquerra 45
        Avanza longitud de rama
        Arbol(Longitud de rama dividida por 2)
        Retrocede longitud de rama
        Gira a la Dreta 90
        Avanza longitud de rama
        Arbol(Longitud de rama dividida por 2)
        Retrocede longitud de rama
        Gira a la Esquerra 45
    Fi del si
Fi del procediment

Una solució en C es la següent: 

#include <graphics.h>
#include <stdio.h>
#include <math.h>
#include <conio.h>

#include <graphics.h>
void PantallaGrafica(void);
void PantallaTexto(void);

void Arbol(float Rama);

double Xinicio=0,Yinicio=0;
double Xfin,Yfin;
double Direccion=0;
double pi;

main(){

        pi=atan(1)*4;
        PantallaGrafica();
        cleardevice();
        Xinicio=(int)(getmaxx()/2); Yinicio=(int)(getmaxy()/2) + 20;
        Direccion=-90;
        Arbol(100);
        getchar();
        PantallaTexto();
}

void Arbol(float Rama){
        if (Rama >= 2) {

                Direccion=Direccion+45;

                //Avanza rama
                Xfin=Xinicio+Rama*cos(pi*Direccion/180);
                Yfin=Yinicio+Rama*sin(pi*Direccion/180);
                line((int)Xinicio,(int)Yinicio,(int)Xfin,(int)Yfin);
                Xinicio=Xfin;Yinicio=Yfin;

                Arbol(Rama/2);

                //Retrocede rama
                Xfin=Xinicio+Rama*cos(pi*Direccion/180 + pi);
                Yfin=Yinicio+Rama*sin(pi*Direccion/180 + pi);
                line((int)Xinicio,(int)Yinicio,(int)Xfin,(int)Yfin);
                Xinicio=Xfin;Yinicio=Yfin;

                Direccion=Direccion-90;

                //Avanza rama
                Xfin=Xinicio+Rama*cos(pi*Direccion/180);
                Yfin=Yinicio+Rama*sin(pi*Direccion/180);
                line((int)Xinicio,(int)Yinicio,(int)Xfin,(int)Yfin);
                Xinicio=Xfin;Yinicio=Yfin;

                Arbol(Rama/2);

                //Retrocede longitud
                Xfin=Xinicio+Rama*cos(pi*Direccion/180 + pi);
                Yfin=Yinicio+Rama*sin(pi*Direccion/180 +pi);
                line((int)Xinicio,(int)Yinicio,(int)Xfin,(int)Yfin);
                Xinicio=Xfin;Yinicio=Yfin;

                Direccion=Direccion+45;
        }
}

void PantallaGrafica(void) {
        int gdriver = DETECT, gmode, errorcode;
        initgraph(&gdriver, &gmode, "");
        errorcode = graphresult();

        if (errorcode != grOk) {
                cprintf("Graphics error: %s\n", grapherrormsg(errorcode));
                cprintf("Press any key to halt:");
                getch();
                exit(1);
        }
}

void PantallaTexto(void) {
        closegraph();
}

11.5. Comentari final

La recursivitat és una estructura de programació molt important que té moltes aplicacions. Una de les aplicacions més importants és el recorregut d'arbres car els algoritmes d'indexació de fitxers més eficients es basen en l'estructura d'abre.

11.6. Exercicis

1.- Fes una funció recursiva que rebi una cadena de caràcters i que els imprimeixi en pantalla de la manera següent:
a)
b)
c)
Tramvia
Tramvi
Tramv
Tram

Tra

Tr

T

Tramvia
ramvia
amvia
mvia

via

ia

a
Tramvia
Travia
Tria
Ta

2.- Fes una funció recursiva que ens digui si un string és un palíndrom o no. Recorda que un palíndrom és una frase que es llegeix igual en un sentit (Esquerra-Dreta) que en l'altre sentit (Dreta-Esquerra).

dabalearrozalazorraelabad

3.- Fes una funció recursiva que ens digui si dos strings són iguals però escrits al contrari l'un de l'altre.

4.- Fibonacci: Les liebres es reprodueixen de la següent manera:

·Des de que neixen fins que tenen fills passen dos mesos.

·Després tenen una parella cada més.
 

Així si partim d'una primera parella podem veure que es reprodueixen de la següent manera:
1r mes
2n mes
3r mes
4t mes
5é mes
2 llebres
4 llebres
6 llebres
10 llebres
16 llebres
Així tenim que cada podem calcular el número de llebres que tenim un cert mes si prenem les que teníem els dos mesos anteriors i les sumem.
Tenim una successió en la que an+2=an+an+1.

 
Fes una funció recursiva que rebi quants mesos han transcorregut i que ens escrigui la taula anterior fins a aquest més.
5.- La funció d'Ackerman es defineix per a valors enters no negatius de m i n de la manera següent:

 
A(0,n) = n +1, A(m,0) = A(m-1,1), A(m,n) = A(m-1,A(m,n-1))
Fes la funció recursiva que rebi m i n i ens calculi A(m,n).