Cost de programes recursius

Per què?

Amb un bucle, el cost és «voltes × cost d’una volta». Amb una funció recursiva no hi ha voltes: hi ha crides, que en fan d’altres, que en fan d’altres… Al capítol de correctesa recursiva vas veure que potencia(x, n/2) * potencia(x, n/2) és correcte però molt més lent que guardar el resultat en una variable. Quant més lent? I la funció de les escales, per què triga tant amb $n = 50$?

Per respondre-ho, cal saber calcular el cost d’una funció recursiva.

La idea: una recurrència

Sigui $T(n)$ el cost de la funció amb una entrada de mida $n$. Una crida fa:

• una feina no recursiva (comparacions, sumes, potser un bucle…), que costa alguna cosa en funció de $n$;
• crides recursives amb mides més petites, que costen $T$ d’aquelles mides.

Escrivim-ho com una equació. Per exemple, la potència ràpida:

long long potencia(long long x, int n) {
    if (n == 0) return 1;
    long long p = potencia(x, n / 2);
    if (n % 2 == 0) return p * p;
    return p * p * x;
}

fa una feina constant i una crida amb $n/2$:

És una recurrència. Desplegant-la: $T(n) = T(n/2) + c = T(n/4) + 2c = T(n/8) + 3c = \dots$ Després de $k$ passos, $T(n/2^k) + kc$, i s’arriba al cas base quan $2^k \approx n$, és a dir, $k \approx \log_2 n$. Per tant, $T(n) = \Theta(\log n)$.

L’arbre de crides

Una altra manera de veure-ho: dibuixa totes les crides que es fan. Cada crida és un node, i els seus fills són les crides que fa. El cost total és la suma de la feina no recursiva de tots els nodes.

Amb la versió que repeteix les crides:

long long potencia(long long x, int n) {
    if (n == 0) return 1;
    if (n % 2 == 0) return potencia(x, n / 2) * potencia(x, n / 2);
    return potencia(x, n / 2) * potencia(x, n / 2) * x;
}

cada crida en fa dues amb $n/2$: $T(n) = 2T(n/2) + \Theta(1)$. L’arbre de crides és un arbre binari complet: de $n$ es baixa a $1$ en uns $\log_2 n$ nivells, i encara n’hi ha un més per al cas $n = 0$. Al nivell $k$ hi ha $2^k$ crides, i en total n’hi ha unes $4n$. Cost $\Theta(n)$: de logarítmic a lineal només per haver repetit una crida. Amb $n = 1024$, la primera versió fa 12 crides i la segona, 4.095.

Amb la funció de Fibonacci (la de les escales és la mateixa idea), l’arbre de crides de fib(4) és:

La recurrència és $T(n) = T(n-1) + T(n-2) + \Theta(1)$, i el nombre de crides creix com els mateixos nombres de Fibonacci, que són aproximadament $1{,}618^n$. Exponencial. Comptant crides de debò: fib(10) en fa 177, fib(20) 21.891 i fib(30) 2.692.537.

Pots veure com creix l’arbre de crides a l’eina «La pila de crides» de dalt de tot.

Els patrons

No cal desplegar cada recurrència. Gairebé totes les de PRO2 encaixen en un d’aquests dos patrons.

Reducció per substracció

La crida recursiva és amb $n - c$ (per exemple, $n - 1$):

A la substracció cal $c \ge 1$. fib no encaixa exactament en el patró de substracció, perquè les crides són amb $n-1$ i $n-2$. Queda entre $2T(n-2)$ i $2T(n-1)$, és a dir, entre $\Theta(\sqrt2^{,n})$ i $\Theta(2^n)$: exponencial (de fet, $\Theta(1{,}618^n)$).

Reducció per divisió

La crida recursiva és amb $n / b$:

Es compara $k$ amb $\log_b a$ (que diu com creix el nombre de crides):

La intuïció: l’arbre de crides té $\log_b n$ nivells, i al nivell de baix hi ha $a^{\log_b n} = n^{\log_b a}$ crides. La feina de l’arrel és $n^k$. Si $n^k$ és més gran, guanya l’arrel. Si és més petit, guanyen les fulles. Si són iguals, tots els nivells costen el mateix, i com que n’hi ha $\log n$, surt el factor $\log n$.

Recorda que el teorema demana $a \ge 1$ i $b > 1$.

És el teorema mestre (a EDA el veuràs amb més detall i demostrat). Pots provar-lo a l’eina «Teorema mestre» de dalt de tot.

Funcions sobre arbres

Amb arbres, la mida dels fills depèn de la forma de l’arbre, i la recurrència és més incòmoda. Però sovint hi ha una manera més fàcil: comptar per nodes. Si la funció fa una crida per node i a cada crida fa una feina constant (sense comptar les crides de dins), el cost és $\Theta(n)$. Així són mida, alcada, suma i tots els recorreguts.

El problema ve quan a cada node es fa una feina que no és constant. Per exemple, per saber si un arbre és equilibrat (a cada node, les alçades dels dos fills difereixen com a molt en 1):

bool equilibrat(const BinTree<int>& a) {
    if (a.empty()) return true;
    bool ee = equilibrat(a.left());
    bool ed = equilibrat(a.right());
    int dif = alcada(a.left()) - alcada(a.right());
    return ee and ed and dif >= -1 and dif <= 1;
}

A cada node es crida alcada sobre els dos fills, i alcada recorre tot el subarbre. Per tant, cada node és recorregut per alcada una vegada per cada avantpassat que té. En un arbre que és una línia (el cas pitjor), el node de profunditat $p$ té $p$ avantpassats: en total $0 + 1 + \dots + (n-1) = \Theta(n^2)$. (En un arbre equilibrat, cada node té $\Theta(\log n)$ avantpassats, i el cost és $\Theta(n \log n)$.)

Es pot fer en $\Theta(n)$: ho veuràs al capítol següent.

Errors habituals

Exercicis

// a)
int f(int n) { if (n <= 1) return 1; return f(n - 1) + 1; }

// b)
int g(int n) { if (n <= 1) return 1; return g(n / 2) + g(n / 2); }

// c) (v té n elements entre esq i dre)
int h(const vector<int>& v, int esq, int dre) {
    if (esq > dre) return 0;
    int s = 0;
    for (int i = esq; i <= dre; ++i) s += v[i];
    return s + h(v, esq + 1, dre);
}

// d)
int k(int n) { if (n <= 1) return 1; return k(n - 1) + k(n - 1); }

// Pre: 0 <= e <= d <= v.size(). Post: v[e..d-1] està ordenat (amb els mateixos elements).
void ordena(vector<int>& v, int e, int d) {
    if (d - e <= 1) return;
    int m = (e + d) / 2;
    ordena(v, e, m);
    ordena(v, m, d);
    vector<int> aux;
    int i = e, j = m;
    while (i < m and j < d) {
        if (v[i] <= v[j]) aux.push_back(v[i++]);
        else aux.push_back(v[j++]);
    }
    while (i < m) aux.push_back(v[i++]);
    while (j < d) aux.push_back(v[j++]);
    for (int k = 0; k < int(aux.size()); ++k) v[e + k] = aux[k];
}