Recursiónc++complejidadrecursiónanálisis

Complejidad de la Recursión

Aprende a analizar la complejidad temporal y espacial de funciones recursivas

OOI Oaxaca9 de febrero de 20264 min read

¿Por qué analizar la recursión?

Cuando escribes una función recursiva, necesitas saber: ¿cuánto tiempo tarda? ¿cuánta memoria usa? Esto es especialmente importante en competencias, donde hay límites estrictos de tiempo y memoria.

Método 1: Árbol de recursión

Dibuja todas las llamadas como un árbol y cuenta:

Factorial: $O(n)$

factorial(5)
└── factorial(4)
    └── factorial(3)
        └── factorial(2)
            └── factorial(1)
                └── factorial(0)  ← caso base

Es una cadena lineal de $n+1$ llamadas. Cada llamada hace $O(1)$ trabajo. Total: $O(n)$ .

Fibonacci (sin memo): $O(2^n)$

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2) ──...
│   │   └── fib(1)
│   └── fib(2) ──...
└── fib(3)
    ├── fib(2) ──...
    └── fib(1)

Es un árbol binario de profundidad $n$ . Tiene hasta $2^n$ nodos. Total: $O(2^n)$ .

Fibonacci (con memo): $O(n)$

Cada valor de 0 a n se calcula exactamente una vez. Total: $O(n)$ .

Método 2: Relación de recurrencia

Expresa el tiempo como una fórmula recursiva y resuélvela:

Ejemplo: Búsqueda binaria

int busqueda(vector<int> &v, int lo, int hi, int x) {
    if (lo > hi) return -1;
    int mid = (lo + hi) / 2;
    if (v[mid] == x) return mid;
    if (v[mid] < x) return busqueda(v, mid+1, hi, x);
    return busqueda(v, lo, mid-1, x);
}

Recurrencia: $T(n) = T(n/2) + O(1)$

En cada llamada, el problema se reduce a la mitad. Después de $k$ pasos, $n / 2^k = 1$ , así que $k = \log_2 n$ .

Total: $O(\log n)$ .

Ejemplo: Merge Sort

void mergeSort(vector<int> &v, int lo, int hi) {
    if (lo >= hi) return;
    int mid = (lo + hi) / 2;
    mergeSort(v, lo, mid);      // Primera mitad
    mergeSort(v, mid+1, hi);    // Segunda mitad
    merge(v, lo, mid, hi);      // Combinar: O(n)
}

Recurrencia: $T(n) = 2T(n/2) + O(n)$

Dos subproblemas de tamaño $n/2$ , más $O(n)$ para combinar. Total: $O(n \log n)$ .

Recurrencias comunes

Recurrencia	Complejidad	Ejemplo
$T(n) = T(n-1) + O(1)$	$O(n)$	Factorial, búsqueda lineal recursiva
$T(n) = T(n-1) + O(n)$	$O(n^2)$	Selection sort recursivo
$T(n) = 2T(n-1) + O(1)$	$O(2^n)$	Fibonacci, torres de Hanoi
$T(n) = T(n/2) + O(1)$	$O(\log n)$	Búsqueda binaria
$T(n) = 2T(n/2) + O(n)$	$O(n \log n)$	Merge sort
$T(n) = 2T(n/2) + O(1)$	$O(n)$	Recorrer árbol binario

Complejidad espacial

La recursión usa espacio en la pila de llamadas. La profundidad máxima de la pila = la profundidad del árbol de recursión.

Función	Profundidad de recursión	Espacio
Factorial	$n$	$O(n)$
Fibonacci (sin memo)	$n$	$O(n)$
Búsqueda binaria	$\log n$	$O(\log n)$
Merge sort	$\log n$	$O(n)$ (por el arreglo auxiliar)

Consejos prácticos

Si la recursión es lineal (una sola llamada recursiva por nivel), la complejidad suele ser simple de analizar.
Si hay dos llamadas recursivas (como Fibonacci), la complejidad crece exponencialmente sin memorización.
Con memorización, la complejidad es: (número de estados) × (trabajo por estado).
En competencias, si $n \leq 20$ , puedes usar $O(2^n)$ . Si $n \leq 10^6$ , necesitas $O(n)$ o $O(n \log n)$ .

Ejercicio de práctica

Analiza la complejidad de esta función. ¿Cuántas veces se imprime "hola"?

void misterio(int n) {
    if (n <= 0) return;
    cout << "hola" << endl;
    misterio(n / 3);
    misterio(n / 3);
}

Ver solución

$T(n) = 2T(n/3) + O(1)$

Usando el teorema maestro con $a=2$ , $b=3$ , $c=0$ : como $\log_3 2 \approx 0.63 > 0$ , la complejidad es $O(n^{\log_3 2}) \approx O(n^{0.63})$ .

En términos simples: crece más rápido que $O(\log n)$ pero mucho más lento que $O(n)$ .

Siguiente paso

Aprende sobre Pilas y Colas, estructuras de datos fundamentales que tienen conexión directa con la recursión.