Aprendre a programar 4 - Paràmetres per referència i recursivitat

Després d'haver fet uns quants programes, és possible que algú s'hagi plantejat la següent pregunta: "Què passa si modifico un paràmetre d'una funció?". Per exemple, què passaria si féssim el següent programa?

void incrementar(int n) {
    ++n;
}
int main() {
    int n;
    cin >>n;
    incrementar(n);
    cout <<n<<endl;
}

Què mostrarà el cout? Apostem?

El cout mostrarà el mateix número que hem introduït. Quan cridem una funció, el que es fa és copiar la variable, per passar-li a la funció. Per això, facis el que facis amb la variable dins de la funció, la original no canviarà. Ara, això també té un problema. Imaginem que tenim la Bíblia en vers dins d'un string (que li diem b). Si fem la funció
void mostrar(string b) {
...
}
Imaginem què serà pel processador copiar tot aquest string, només per mostrar-lo. Un cost massa gran. Per això es van inventar les referències.

Referències

Què és una referència? He escrit un article més extens sobre el tema, que està aquí, però en faré un petit resum. Bàsicament, és una variable que no conté cap valor per si mateixa, sinó que fa referència a un altre. Per exemple, si féssim 

string s="Hola!"

char& c=s[3];

c='i';

cout <<s<<endl;

Quan executéssim, per la sortida veuríem "Holi!". Això és perquè c, en realitat, no contenia la lletra a, sinó que apuntava al quart element del string (recordem que comencem a comptar pel 0). Això també ho podem utilitzar amb les funcions

void incrementar(int& n) {
    ++n;
}
int main() {
    int n;
    cin >>n;
    incrementar(n);
    cout <<n<<endl;
}

Si executem això, enlloc de mostrar-nos la n que hem introduït, ens mostrarà n+1, ja que ara sí que hem modificat la variable original. De la mateixa manera, si tinguéssim el codi

void mostrar (string& b){
...
}
No copiaria tota la Bíblia en vers, sinó que només hauria d'indicar-li a la funció on trobar aquesta variable. I, en C++, les adreces acostumen a ocupar el mateix que un int.
No obstant, en casos així, si ho passem per referència per un tema de cost, però no volem modificar-la, el que podem fer és passar-la per referència constant. Això fa que no la puguem modificar, evitant-nos problemes després (què passa si la modifiquem sense voler?). Es fa amb la paraula clau "const"

void mostrar(const string& b) {
...
}

Recursivitat

Imaginem que volem fer una funció que calculi n!. Sabem que la definició de n! en el món dels nombres majors o iguals a 0 és

Si (n=0), n!=1

Si no, n!=n*(n-1)!

Això és una definició recurrent. Defineix una funció utilitzant-se a ella mateixa. Concretament, és una recurrència substractora. Us imagineu traslladar aquesta definició al nostre codi? Ho podem fer, una mica com a experiment

int factorial(int n) {

    if(n==0) return 1;

    return n*factorial(n-1);

}

Sembla que és una traducció bastant igual. Us imagineu que això funcionés? Doncs no cal imaginar, ja que funciona. El que fa és que, si n és més gran que 0 (suposem que mai serà menor), calcula factorial(n-1), ho multiplica per n, i ho retorna. Un exemple seria:

5!=5*4!=5*4*3!=5*4*3*2!=5*4*3*2*1!=5*4*3*2*1*0!=5*4*3*2*1*1=120

Les Torres de Hanoi

Com es faria per moure una torre de n discs del piló 1 al 3? Mouríem primer els n-1 discs de dalt al piló 2, mouríem el disc de sota de tot al piló 3, i finalment mouríem els n-1 discs del piló 2 al 3. Per tant, això ho podem passar a codi.

void torres_hanoi(int A, int B, int C, int n) {

    if (n==0) return;

    torres_hanoi(A,C,B,n-1);

    cout <<A<<"->"<<C<<endl;

    torres_hanoi(B,A,C,n-1);

}

El que fa aquest codi és que, si n==0, sortim de la funció, ja que si no volem moure cap disc, no cal fer res. Movem n-1 discs de A a B, movem la base de A a C, i movem els n-1 discs de nou de B a C.

Estic segur que algú ha intentat fer un bucle súper complex, ja que és el que jo vaig fer, i resulta que realment es pot fer amb una funció de 4 línies. Ja ho diuen, iterar és màgic, però la recursivitat és divina

Com a curiositat, per moure n discs, s'han de fer 2^n-1 moviments. És a dir, els monjos de Hanoi hauran de fer 18.446.744.073.709.551.615 moviments. Uns 35 bilions d'anys (bilions europeus, amb 12 zeros), si fan un moviment cada minut. És a dir, de moment no cal preocupar-se per si els monjos acaben de desplaçar les torres o no

Comptar dígits recursivament

Imaginem que volem comptar els dígits d'un número. La primera funció que ens vindria al cap seria iterativa, i seria una cosa així:

int nombre_digits(int n) {

    int r=1;

    while(n>10) {

        ++r;

        n/=10;

    }

    return r;

}

No obstant, també podem programar una versió recursiva, que podria ser una cosa així:

int nombre_digits(int n) {

    if(n<10) return 1;

    return 1+nombre_digits(n/10);

}

Suposo que es veu clar, no? Si n és menor que 10, sabem que és un dígit. Si no, sabem que dividint entre 10, tindrà un dígit menys

Com a curiositat, això és el que en matemàtiques en diríem una recurrència divisora. Si ens fixem, a les anteriors, quan fèiem la crida recursiva, reduíem el cas original restant-li una constant k (que en els dos casos era 1). Aquí, en canvi, dividim per 10. En termes d'eficiència, acostumen a ser millors les divisores (en el cas n=100.000 faríem 6 crides recursives per comptar els dígits, mentre que per fer el factorial, en faríem 100.000. En cost, diríem que la del factorial té cost Θ(n), mentre que la de comptar dígits té un cost Θ(log n). Això és perquè la primera, el cost creix proporcionalment a n, mentre que a la segona, creix proporcionalment al logarítme de n. Això fa que, a la llarga, una funció Θ(log n) sigui molt més ràpida que una Θ(n), ja que una lineal creix molt més ràpid que una logarítmica. No obstant, això fins a EDA no es fa, així que no ens hem de preocupar de com es calcula

Fibonacci

Ara que ja en portem unes quantes, oi que podríeu fer una funció recursiva que calculi l'element n de la successió de Fibonacci?

Fem una mica de memòria. La successió de Fibonacci és aquella on el primer element és 1, i la resta, la suma dels dos anteriors. 

1-1-2-3-5-8-13-21-34-55-89...

Es pot definir recurrentment, dient que

Si n=0 o n=1, fib(n)=n

Si no, fib(n)=fib(n-1)+fib(n-2)

El punt de si n=0 és perquè quedi clar que l'element 2 de la successió és 1 (1+0). Per programar també ens pot ser d'ajuda

Aleshores, amb aquesta informació, podríeu fer una funció recursiva que calculi l'element n de la successió?

RESULTAT:

Estic segur de que la solució que heu trobat és una cosa similar a això:

int fib(int n) {

    if(n==0 or n==1) return n;

    return fib(n-1)+fib(n-2);

}

Ara podem intentar calcular l'element 50 de la successió. Quant creieu que trigarà? Jo dic que us cansareu d'esperar a que el calculi. Aquesta funció és la típica que s'utilitza per criticar la recursivitat. Si fem el càlcul (ja us l'estalvio jo), aquesta funció té cost Θ(Φ^n), sent Φ el nombre auri. És a dir, molt cost. Com que una imatge val més que mil paraules, una representació gràfica dels càlculs que fa per calcular fib(7), que he trobat per internet.

 I sempre hi ha el típic que diu "ei, jo sé fer una versió iterativa que té cost lineal, perquè els codis recursius són molt més lents que els iteratius". Bé, sí, són una mica més lents, però aquest exemple és fal·laç. Perquè sí, aquesta versió recursiva té un cost horrible, però perquè està mal feta. Una funció recursiva ben feta, té cost logarítmic. 

pair<int,int> fib_lineal(int n) {

    if (n<2) return pair<int,int>(n,0);

    pair<int,int> aux=fib_lineal(n-1);

    return pair<int,int>(aux.first+aux.second,aux.first);

}

Sorpresa! Una versió lineal, que res té a envejar a la iterativa. 

Nota: les pairs són una manera d'emmagatzemar dues variables en una. Quan fem tuples explicaré més com van, però en essència, pair<T1,T2> p serveix per crear una variable que emmagatzema dins dues variables. p.first és de tipus T1, p.second de tipus T2. Ho faig així perquè puc retornar els dos elements anteriors, i així només cal fer una crida recursiva

Si a algú li interessa, hi ha una versió recursiva en temps logarítmic aquí

Operacions amb parèntesis

Aquí farem un problema del Concurs de Programació de la FIB. Concretament, el P45102. El que ens diu és que rebrem una expressió. Una expressió pot ser, o bé un número, o bé una operació de dues expressions, posada entre parèntesis. Uns exemples d'expressions serien

9

( 1 + 3 )

( ( 3 - 5 ) * ( ( 7 * 2 ) + 5 ) )

El problema ens demana que fem un programa que llegeixi això, i ens mostri el resultat d'avaluar aquesta expressió. Ho podríem fer així:

bool es_simbol(char c) {
return c=='+' or c=='-' or c=='*';
}

int cercar_operand (const string& s, int l, int r) {
int oberts=0;
for (int i=l+2;i<=r-2;++i) {
if (s[i]=='(') ++oberts;
else if (s[i]==')') --oberts;
if (oberts==0 and es_simbol(s[i])) return i;
}
return -1; //Aquí no arribem, però així no dóna warning
}

int avaluar (const string& s, int l, int r) {
if (l==r) return s[l]-'0';
int operand=cercar_operand(s,l,r);
if (s[operand]=='+') {
return avaluar(s,l+2,operand-2)+avaluar(s,operand+2,r-2);
}
if (s[operand]=='-') {
return avaluar(s,l+2,operand-2)-avaluar(s,operand+2,r-2);
}
return avaluar(s,l+2,operand-2)*avaluar(s,operand+2,r-2);
}

int avaluar(const string& s) {
return avaluar(s,0,s.size()-1);
}

int main () {
string s;
getline(cin,s);
cout <<avaluar(s)<<endl;
}

Tenim una funció avaluar que rep un string, que serveix per fer més maco el main. La important és la que rep un string i dos enters. Aquesta avalua l'expressió que va de l a r. Si l==r, vol dir que és un dígit, retornem el seu valor i ja. Si no, vol dir que és una operació, busquem el seu signe, avaluem l'expressió de la dreta, la de l'esquerra, i operem. 

Elevar recursivament

Ara podem posar un últim exemple (de moment). Més endavant en veurem uns quants més. Fem una funció recursiva

int exp(int a, int n);

Que calculi a^n recursivament. La solució, a sota

int exp(int a, int n) {

    if (n==0) return 1;

    return a*exp(a,n-1);

}

Suposo que el que haureu fet és alguna cosa així. Una versió que s'aprofita de que a^n=a^(n-1)*a. És a dir, una recurrència substractora. És el que es pot demanar a PRO1, no obstant, hi ha una manera molt més òptima de fer-ho. Sabem que a^n=a^(n/2)*a^(n/2), no? Doncs per què no aprofitar-nos d'això?

int exp(int a, int n) {

    if(n==0) return 1;

    int aux=exp(a,n/2);

    if(n%2==0) return aux*aux;

    return aux*aux*a;

}

Aquí el que fem és aprofitar-nos d'aquella propietat. Si n és parell, dividint no perdrem res, i per tant, retornem a^(n/2)*a^(n/2). Si és senar, al ser la divisió entera, perdrem 1 (3/2=1, es perd 1). Per tant, retornem a^(n/2)*a^(n/2)*a, i ja tenim el resultat en temps logarítmic. Això és l'algorisme d'Exponenciació Ràpida, un algorisme del tipus "divide and conquer". En farem algun més en algun altre moment

Nota: No serveix posar "return exp(a,n/2)*exp(a,n/2)". Això faria que, per cada crida recursiva en féssim 2, transformant-se en una funció amb cost lineal.

Recursivitat en el món informàtic

Entre els informàtics, hi ha dos tipus de persona. Els primers, els que els encanta la recursivitat. Els segons, els que la odien. Jo personalment sóc dels primers, sóc molt fan d'ella. I, per tant, molts informàtics la colen a tot arreu on poden. No em creieu?

Sabeu què és GNU? Sabeu de què és l'acrònim? És l'acrònim de GNU's Not Unix. És a dir, és un acrònim recursiu

Sabeu el format PNG? És un format d'imatges molt típic. Doncs és l'acrònim de PNG's Not GIF. Sí, ara et diuen que és de Portable Network Graphics, però que no nos engañen

Wine, el programa per executar aplicacions de Windows a Linux, és l'acrònim de Wine Is Not an Emulator

Bing, el buscador de Microsoft. Existeix el mite no confirmat de que és l'acrònim de Bing Is Not Google. També hi ha gent que creu que és l'acrònim de Because I'm Not Google. 

Recursivitat i Google

Ja hem vist que Bing li té certa mania a Google, i ho expressa recursivament. Quina és la relació de Google amb la recursivitat?

Recursivitat fora de la informàtica

La recursivitat també s'utilitza fora de la informàtica. Per exemple, s'utilitza per calcular el nombre auri (φ). Hi ha una propietat, que diu que 

φ=1+1/φ

Això ens permet definir-lo de manera recursiva. Podem fer un programa així

double fi(int crides) {

    if (crides==0) return 1;

    return 1+1/fi(crides-1);

}

Com més gran sigui crides, més proper serà el resultat. Fixem-nos que si és 0, ens donarà 1, i si és 1, ens donarà 2. No obstant, amb 4 ja ens dóna 1,6, amb 9 dóna 1.61818, i podem anar seguint

En el proper article, us parlaré del tractament seqüencial, i de com evitar fer iteracions de més. No obstant, si has entès bé la recursivitat, veuràs que cada cop faràs menys fors i whiles, per passar-te a funcions recursives