CP-UPV Bootcamp - Capítulo 4

Capítulo 4: Recursión

Índice de contenidos

• Definición de recursión
• Funcionamiento (Call Stack)
• Tipos de recursión
• Coste temporal y espacial
• El Teorema Maestro
• Ejemplo 1: Tetris Espacial
• Ejemplo 2: El juez de Rubén
• Problemas de práctica

Definición de recursión

La recursión es una técnica de programación en la que una función se llama a sí misma para resolver un problema. La idea central es dividir un problema complejo en subproblemas más pequeños de la misma naturaleza.

Para que una función recursiva sea correcta y no se ejecute infinitamente, debe cumplir dos condiciones esenciales:

• Caso Base: La condición de parada que resuelve un subproblema de manera directa sin hacer más llamadas recursivas.
• Caso General (o Recursivo): La parte donde la función se llama a sí misma con un argumento modificado que se acerca progresivamente hacia el caso base.

Funcionamiento (Call Stack)

Cuando una función se ejecuta, el sistema operativo utiliza una estructura de datos interna llamada Call Stack (Pila de llamadas). Cada vez que una función se llama a sí misma, se añade una nueva entrada (un stack frame) en el tope de la pila, congelando la ejecución de la función anterior.

Si la recursión no alcanza nunca el caso base o hace demasiadas llamadas consecutivas, la memoria asignada al Call Stack se agota, provocando el famoso error de desbordamiento de pila o Stack Overflow.

Tipos de recursión

Dependiendo de cómo esté estructurado el flujo del algoritmo, de cuántas veces se invoque a sí misma la función y del lugar exacto donde ocurra la llamada, podemos clasificar la recursión en tres categorías críticas para el rendimiento:

1. Recursión Lineal

Es el tipo más simple. La función realiza, como máximo, una única llamada recursiva por cada ejecución del caso general. El estado del problema avanza paso a paso de forma secuencial.

Impacto en memoria: Genera un Call Stack completamente vertical. Si la función procesa una entrada de tamaño $N$, la pila de llamadas crecerá linealmente hasta alcanzar una profundidad de $O(N)$ elementos antes de empezar a liberar memoria.

// Ejemplo clásico: Cálculo del Factorial N!
long long factorial(int n) {
    if (n <= 1) return 1; // Caso base
    return n * factorial(n - 1); // Una sola llamada lineal
}

2. Recursión Múltiple

Ocurre cuando el caso general de una función contiene dos o más llamadas recursivas independientes. En lugar de procesar el problema en una línea recta, el flujo de ejecución se ramifica constantemente.

Impacto en complejidad: Esta ramificación transforma la traza de ejecución en un árbol de recursión. El peligro principal aquí es la redundancia de cálculos: un algoritmo de recursión múltiple ingenuo (como calcular el número de Fibonacci sin programación dinámica) repite subproblemas idénticos una y otra vez, disparando la complejidad temporal a un coste exponencial de $O(2^N)$.

// Ejemplo clásico: Serie de Fibonacci ingenua
int fibonacci(int n) {
    if (n <= 1) return n; // Casos base
    // Dos llamadas recursivas independientes -> Ramificación binaria
    return fibonacci(n - 1) + fibonacci(n - 2); 
}

3. Recursión de Cola (Tail Recursion)

La recursión de cola es un caso especial sumamente codiciado en optimización. Decimos que una función es recursiva de cola si la llamada recursiva es la última instrucción absoluta que ejecuta la función.

Fíjate bien en la diferencia con la recursión lineal clásica: en el ejemplo del factorial, al volver de la llamada factorial(n-1), el ordenador todavía tiene que multiplicar ese resultado por n. Por lo tanto, el sistema no puede destruir el stack frame actual porque aún le queda trabajo por hacer. En cambio, en la recursión de cola, al no quedar operaciones pendientes, el valor devuelto por la subllamada es directamente el resultado final.

La magia del compilador (Tail Call Optimization - TCO): Compiladores modernos (como g++ con flags de optimización como -O2 o -O3) detectan esta propiedad. Al ver que la función actual ya no tiene tareas pendientes, en lugar de empujar un nuevo bloque a la pila y arriesgarse a un Stack Overflow, el compilador reutiliza el mismo stack frame matemático modificando únicamente las variables locales. Esto reduce mágicamente el coste espacial del Call Stack de $O(N)$ a un coste constante de $O(1)$ en espacio, igualando la eficiencia de un bucle iterativo.

// Versión optimizada de Factorial usando un acumulador para lograr Recursión de Cola
long long factorialCola(int n, long long acumulador = 1) {
    if (n <= 1) return acumulador; // Caso base: devolvemos directamente el resultado acumulado
    
    // La llamada recursiva es la última acción. No hay operaciones pendientes al regresar.
    return factorialCola(n - 1, n * acumulador); 
}

Coste temporal y espacial

Analizar la complejidad de una función recursiva requiere entender cómo se expanden las llamadas:

• Complejidad Temporal: Se puede calcular modelando la relación de recurrencia mediante un árbol de recursión o aplicando el Teorema Maestro. Por ejemplo, una recursión lineal que recorre un array suele costar $O(N)$, mientras que una recursión doble descontrolada (como Fibonacci ingenuo) puede dispararse a $O(2^N)$.
• Complejidad Espacial: Aunque no declares variables adicionales, la profundidad máxima del árbol de recursión determina el tamaño máximo que alcanzará el Call Stack. Si la recursión llega a una profundidad de $N$ niveles, el coste espacial en la pila de llamadas será de $O(N)$.

El Teorema Maestro

Para algoritmos de tipo Divide y Vencerás que dividen el problema en subproblemas del mismo tamaño, el Teorema Maestro proporciona una solución matemática directa para calcular la complejidad temporal sin necesidad de dibujar todo el árbol de llamadas.

Se aplica a ecuaciones de recurrencia que siguen la forma:

Donde:

• $a \ge 1$: Número de subproblemas (cuántas llamadas recursivas se abren).
• $b > 1$: Factor por el que se divide el tamaño del problema en cada nivel.
• $f(n)$: Coste del trabajo extra realizado en la función localmente (fuera de la recursión).

Para determinar la complejidad final, comparamos el crecimiento de $f(n)$ con el término límite $n^{\log_b a}$:

• Caso 1 (Dominio recursivo): Si las subllamadas crecen más rápido que el trabajo local ($f(n) < n^{\log_b a}$), la complejidad es $O(n^{\log_b a})$.
• Caso 2 (Equilibrio perfecto): Si ambos términos crecen al mismo ritmo ($f(n) = \Theta(n^{\log_b a})$), la complejidad final es $O(n^{\log_b a} \log n)$. (Ejemplo: Merge Sort o Búsqueda Binaria).
• Caso 3 (Dominio local): Si el trabajo extra local absorbe el coste del árbol ($f(n) > n^{\log_b a}$), la complejidad es $O(f(n))$.

Ejemplo 1: Tetris Espacial

El problema Tetris Espacial es una variante original desarrollada por nosotros, basada íntegramente en la lógica fundamental del clásico rompecabezas de las Torres de Hanói. En esta versión, disponemos de una base espacial con tres módulos: el Taller (1), el Hangar (2) y el Módulo de Ataque (3). Un conjunto de $N$ naves de combate se encuentran apiladas inicialmente en el Taller ordenadas rígidamente por tamaño, de forma que una nave grande nunca puede colocarse encima de una más pequeña para evitar destrucciones.

El objetivo es trasladar la pila completa de naves desde el Taller (1) hasta el Módulo de Ataque (3), cumpliendo estrictamente que solo se puede mover una única nave superior por movimiento y respetando siempre la restricción de tamaños. El programa debe calcular el número mínimo total de movimientos indispensables y detallar la secuencia exacta de pasos (módulo de origen y módulo de destino) para efectuar el traslado con éxito.

#include <bits/stdc++.h>
using namespace std;

void torres(int n, int origen, int destino, int auxiliar) {
    if (n == 0) return;  // Es el caso base necesario en la recursión!!

    torres(n - 1, origen, auxiliar, destino); // Movemos las n - 1 naves al hangar auxiliar

    cout << origen << " " << destino << "\n";

    torres(n - 1, auxiliar, destino, origen); // Movemos las n - 1 naves del auxiliar al destino final
}

int main() {
    // Primero tenemos las líneas de optimización para la programación competitiva
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    int k = (1 << n) - 1; // El total de movimientos es 2^n - 1
    cout << k << '\n';

    // Ahora mostramos el recorrido con la función recursiva
    torres(n, 1, 3, 2);

    return 0;
}

import sys

def torres(n, origen, destino, auxiliar):
    if n == 0: return # Caso base de la recursión

    torres(n - 1, origen, auxiliar, destino) # Movemos las n - 1 naves al auxiliar

    print(origen, " ", destino)

    torres(n - 1, auxiliar, destino, origen) # Movemos las n - 1 naves del auxiliar al destino

# Entrada rápida de datos en python
data = sys.stdin.read().split()
it = iter(data)

n = int(next(it))
print((1 << n) - 1)

torres(n, 1, 3, 2)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {
    
    public static void torres(int n, int origen, int destino, int auxiliar, PrintWriter out) {
        if (n == 0) return;  // Es el caso base

        torres(n - 1, origen, auxiliar, destino, out); // Movemos las n - 1 naves al hangar auxiliar

        out.println(origen + " " + destino);

        torres(n - 1, auxiliar, destino, origen, out); // Movemos las n - 1 naves del auxiliar al destino final
    }

    public static void main(String[] args) throws IOException {
        // Líneas de optimización para la programación competitiva
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st = null;

        String line = br.readLine();
        if (line != null) {
            st = new StringTokenizer(line);
            int n = Integer.parseInt(st.nextToken());

            int k = (1 << n) - 1; // El total de movimientos es 2^n - 1
            out.println(k);

            // Ahora mostramos el recorrido con la función recursiva
            torres(n, 1, 3, 2, out);
        }
        
        // Es fundamental vaciar el buffer al final para asegurar que todo se imprima correctamente
        out.flush();
    }
}

Ejemplo 2: El Juez de Rubén

El gran dictador Rubén Nieto está intentando desarrollar su propio juez de programación competitiva. Durante el proceso ha descubierto que si altera el orden de las operaciones matemáticas escribiéndolas en notación polaca (por ejemplo, * + 7 4 5 en lugar de (7 + 4) * 5), el juez pasa a ser un 200% más eficiente.

Como su trabajo en MercaJoja apenas le deja tiempo, nos ha delegado la tarea de evaluar correctamente estas expresiones. El formato garantiza que los únicos operadores son binarios (+, -, *, /) y que la división debe comportarse como la división entera de C++ (truncada hacia cero).

#include <iostream>
#include <string>

using namespace std;

// Leemos elemento a elemento directamente del stream estándar (cin)
long long resolver() {
    string s;
    if (!(cin >> s)) return 0;

    // Si encontramos operador, llamamos recursivamente para ambos operandos
    if (s == "+" || s == "-" || s == "*" || s == "/") {
        long long izq = resolver();
        long long der = resolver();

        if (s == "+") return izq + der;
        if (s == "-") return izq - der;
        if (s == "*") return izq * der;
        if (s == "/") return izq / der; // En C++ la división entera ya trunca hacia cero
    }

    // Si es un número lo convertimos a entero de 64 bits
    return stoll(s);
}

int main() {
    // Optimización estándar de I/O para CP
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cout << resolver() << "\n";

    return 0;
}

import sys

# Aumentamos el límite por si la expresión viniera muy descompensada en profundidad
sys.setrecursionlimit(2000)

def resolver(elementos, idx):
    cad = elementos[idx[0]]
    idx[0] += 1
    
    # Si es un operador, evaluamos primero la parte izquierda y luego la derecha
    if cad in ("+", "-", "*", "/"):
        izq = resolver(elementos, idx)
        der = resolver(elementos, idx)
        
        if cad == "+": return izq + der
        if cad == "-": return izq - der
        if cad == "*": return izq * der
        if cad == "/": return int(izq / der)  # int() para truncar a cero estilo C++
    
    # Si no es operador, es un número
    return int(cad)

def main():
    linea = sys.stdin.read().strip()
    if not linea:
        return
    
    elementos = linea.split()
    idx = [0]  # Pasamos un índice por referencia usando una lista
    print(resolver(elementos, idx))

if __name__ == "__main__":
    main()

import java.util.Scanner;

public class Main {

    // Pasamos el Scanner para ir consumiendo la entrada en orden de forma recursiva
    private static long resolver(Scanner sc) {
        if (!sc.hasNext()) return 0;
        
        String s = sc.next();

        if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
            long izq = resolver(sc);
            long der = resolver(sc);

            if (s.equals("+")) return izq + der;
            if (s.equals("-")) return izq - der;
            if (s.equals("*")) return izq * der;
            if (s.equals("/")) return izq / der; // En Java también trunca hacia cero
        }

        return Long.parseLong(s);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        if (sc.hasNext()) {
            System.out.println(resolver(sc));
        }
        sc.close();
    }
}

Problemas de práctica

La única forma de dominar la recursión es escribiendo código. Te recomendamos resolver la lista de problemas que encontrarás en nuestro bootcamp en codeforces.