Sesión 09: Grokking Algorithms (Capítulo 3) — Recursión y el Call Stack en Rust y Python#

Navegación rápida:

• ← Sesión 08: Memoria y Selection Sort
• Sesión 10: Runner Technique y Duplicados en Listas Enlazadas →
• Glosario Maestro
• Guía de Diagramas de Arquitectura
• Tiempo estimado de estudio: 50-65 minutos.
• Código fuente compilado y probado: practica-rust/dia_09.rs

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

La recursión suele parecer magia o un bucle misterioso, pero a nivel de hardware no es más que una función llamando a una subrutina y apilando marcos en el Stack. Consulta el Glosario Maestro.

Recursión (Recursion)#

• (a) En palabras simples (intuición): Una muñeca rusa (matrioshka). Abres una muñeca grande y dentro hay otra muñeca idéntica pero más pequeña. Sigues abriendo muñecas hasta que llegas a una tan chiquita que ya no se puede abrir (el caso base).
• (b) Definición técnica paso a paso: Técnica de diseño algorítmico donde una función se resuelve invocándose a sí misma con una versión estrictamente más pequeña del mismo problema. Requiere dos componentes indispensables:

1. Caso Base: Condición terminal que devuelve una respuesta inmediata sin hacer más llamadas.
2. Caso Recursivo: Paso que reduce la entrada y realiza la auto-invocación.

• (c) Cómo funciona en Rust (memoria y tipos): Cada invocación emite una instrucción call en ensamblador x86_64, reservando un nuevo marco de pila (Stack Frame) en memoria.
• (d) Error típico de Junior: Olvidar el caso base o escribir un paso recursivo que no reduce la entrada hacia el caso base, provocando un bucle infinito que aborta el programa por Stack Overflow.

Call Stack (Pila de Llamadas del Hilo)#

• (a) En palabras simples (intuición): Un bloc de notas donde anotas en qué página de tu libro te quedaste antes de ir a contestar el teléfono. Cuando cuelgas el teléfono, lees tu nota y retomas la lectura exactamente en esa página.
• (b) Definición técnica paso a paso: Segmento de memoria LIFO (Last-In, First-Out) gestionado directamente por el hardware de la CPU. Cuando la función A invoca a B, la CPU guarda la dirección de instrucción siguiente (RIP), los registros y las variables locales de A. Al terminar B, la instrucción ret restaura el estado y salta de vuelta a A.
• (c) Cómo funciona en Rust (memoria y tipos): La pila tiene un tamaño fijo prefijado por el sistema operativo (típicamente 2 MB en Linux y 1 MB en Windows para hilos secundarios).
• (d) Error típico de Junior: Creer que las variables locales de una función recursiva son compartidas entre llamadas. Cada llamada tiene su propio conjunto privado de variables locales en su respectivo marco.

Desbordamiento de Pila (Stack Overflow)#

• (a) En palabras simples (intuición): Intentar meter 1,000 platos en una alacena donde solo caben 50. La pila de platos choca contra el techo y todo se derrumba.
• (b) Definición técnica paso a paso: Condición de error fatal donde el puntero de pila (RSP) sobrepasa el límite asignado para la memoria del Stack, tocando una página de memoria protegida (guard page). El sistema operativo genera una interrupción de fallo de segmentación (SIGSEGV o excepción 0xC00000FD en Windows) y aborta el proceso de inmediato.
• (c) Cómo funciona en Rust (memoria y tipos): Rust coloca páginas de guardia (guard pages) al final del stack de cada hilo. Un stack overflow no provoca corrupción silenciosa de memoria, sino un aborto seguro del ejecutable.
• (d) Error típico de Junior: Usar recursión profunda para procesar árboles o listas desbalanceadas de 500,000 elementos sin convertir el algoritmo a un bucle iterativo o trasladar la pila al Heap (Vec).

Slicing de Cero Coste (&slice[1..])#

• (a) En palabras simples (intuición): Señalar con el dedo a partir de la segunda persona de una fila en lugar de hacer que todas las personas se muden a una sala nueva.
• (b) Definición técnica paso a paso: En Rust, rebanar un slice &slice[1..] toma tiempo constante O(1) y espacio auxiliar O(1): simplemente crea un nuevo descriptor de 16 bytes en el Stack sumando size_of::<T>() al puntero base y restando 1 a len.
• (c) Cómo funciona en Rust (memoria y tipos): En marcado contraste con Python (donde arr[1:] clona y crea una lista completamente nueva en el Heap en tiempo O(N)), en Rust el sub-slice no clona ni copia nada en memoria.
• (d) Error típico de Junior: Escribir en Python algoritmos recursivos con arr[1:] creyendo que son O(N), cuando la clonación repetida eleva el costo total real a O(N²) tiempo y espacio.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

La Matemática de la Recursión: Inducción Matemática#

La corrección formal de un algoritmo recursivo se fundamenta en el principio de inducción matemática:

1. Caso Base: Demostramos que el algoritmo es correcto para el tamaño mínimo N = 0 o N = 1.
2. Hipótesis de Inducción: Asumimos que el algoritmo funciona correctamente para cualquier tamaño k < N.
3. Paso Inductivo: Demostramos que combinando la solución del problema de tamaño N - 1 con el elemento actual, la solución para tamaño N es formalmente correcta.

Ejemplo Clásico: Factorial (N!)#

Anatomía del Call Stack en la Evaluación de factorial(3)#

Observa cómo las llamadas se apilan hacia arriba hasta alcanzar el caso base, y luego se desapilan calculando los retornos:

FASE 1: APILAMIENTO (DOWNWARD DESCENT)
Llamada 1: factorial(3) -> Espera el resultado de factorial(2)
  Llamada 2: factorial(2) -> Espera el resultado de factorial(1)
    Llamada 3: factorial(1) -> ¡Caso Base! Retorna 1 de inmediato.

FASE 2: DESAPILAMIENTO Y MULTIPLICACIÓN (UNWINDING)
    Llamada 3 finaliza: retorna 1 al marco 2.
  Llamada 2 reanuda: calcula 2 * 1 = 2. Retorna 2 al marco 1.
Llamada 1 reanuda: calcula 3 * 2 = 6. Retorna 6 al llamador original.

3. Visualización Paso a Paso y Gráfica de Memoria en Rust#

Flujo del Call Stack en Factorial#

Consulta la visualización de arquitectura en los diagramas del sistema:

• Gráfico SVG: ![Visualización del Día 09 y Memoria en Rust](../diagrams/sesiones/dia_09.svg)
• Enlace al código fuente Mermaid: Fuente Mermaid

flowchart TD
    F3["fact(3) invoca fact(2)"] --> F2["fact(2) invoca fact(1)"]
    F2 --> F1["fact(1): CASO BASE retorna 1"]
    F1 -.->|Retorna 1| RET2["fact(2) calcula 2 * 1 = 2"]
    RET2 -.->|Retorna 2| RET3["fact(3) calcula 3 * 2 = 6"]

Visualización Cuadro por Cuadro de Memoria: Inversión Iterativa de Lista Enlazada#

Entrada: 1 -> 2 -> 3 -> None. Tres punteros: prev = None, curr = head, next.

ESTADO INICIAL:
prev = None
curr = [1] -> [2] -> [3] -> None

PASO 1:
- next = curr.next.take() -> next = [2] -> [3]
- curr.next = prev        -> [1] -> None
- prev = curr             -> prev = [1] -> None
- curr = next             -> curr = [2] -> [3]

PASO 2:
- next = curr.next.take() -> next = [3]
- curr.next = prev        -> [2] -> [1] -> None
- prev = curr             -> prev = [2] -> [1] -> None
- curr = next             -> curr = [3]

PASO 3:
- next = curr.next.take() -> next = None
- curr.next = prev        -> [3] -> [2] -> [1] -> None
- prev = curr             -> prev = [3] -> [2] -> [1] -> None
- curr = None             -> Bucle finaliza.

Resultado final retornado: prev ([3] -> [2] -> [1] -> None).
Memoria auxiliar: O(1) in-place estricto.

4. Implementación Canónica en Rust + Comparativa con Python#

Implementación en Rust (practica-rust/dia_09.rs)#

//! Implementación canónica de Recursión y manipulación de listas en Rust.
//! Compilable y verificable con `rustc --test`.

#[derive(Debug, PartialEq, Eq, Clone)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}

/// Factorial recursivo clásico O(N) tiempo y O(N) espacio de Stack.
pub fn factorial_recursive(n: u64) -> u64 {
    if n <= 1 {
        1
    } else {
        n * factorial_recursive(n - 1)
    }
}

/// Factorial iterativo O(N) tiempo y O(1) espacio auxiliar.
pub fn factorial_iterative(n: u64) -> u64 {
    let mut acc = 1;
    for i in 2..=n {
        acc *= i;
    }
    acc
}

/// Suma recursiva sobre slices contiguos sin clonar datos en memoria O(1) memoria por marco.
pub fn recursive_sum(slice: &[i32]) -> i32 {
    if slice.is_empty() {
        0
    } else {
        slice[0] + recursive_sum(&slice[1..])
    }
}

/// Inversión de lista enlazada iterativa canónica en O(1) memoria auxiliar.
pub fn reverse_linked_list_iterative(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut prev = None;
    let mut curr = head;

    while let Some(mut node) = curr {
        let next = node.next.take();
        node.next = prev;
        prev = Some(node);
        curr = next;
    }

    prev
}

/// Inversión de lista enlazada recursiva en O(N) memoria de Call Stack.
pub fn reverse_linked_list_recursive(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    fn helper(
        curr: Option<Box<ListNode>>,
        prev: Option<Box<ListNode>>,
    ) -> Option<Box<ListNode>> {
        match curr {
            None => prev,
            Some(mut node) => {
                let next = node.next.take();
                node.next = prev;
                helper(next, Some(node))
            }
        }
    }
    helper(head, None)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_factorial() {
        assert_eq!(factorial_recursive(5), 120);
        assert_eq!(factorial_iterative(5), 120);
    }

    #[test]
    fn test_recursive_sum() {
        assert_eq!(recursive_sum(&[2, 4, 6]), 12);
        assert_eq!(recursive_sum(&[]), 0);
    }
}

Implementación Canónica en Python (practica/dia_09_recursion_call_stack.py)#

def factorial_recursive(n: int) -> int:
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)

def recursive_sum(arr: list) -> int:
    if not arr:
        return 0
    # CUIDADO: En Python arr[1:] clona la lista en O(N)
    return arr[0] + recursive_sum(arr[1:])

5. Las 3 Trampas Clásicas en Entrevistas#

1. La Clonación Oculta en Slices de Python: - En Python, arr[1:] crea un duplicado de la lista restante. Si llamas recursive_sum(arr[1:]) recursivamente N veces, realizas N + (N-1) + … + 1 = O(N²) copias de memoria en el Heap. En Rust, &slice[1..] es una simple ventana prestada de 16 bytes en Stack sin costo de copia.
2. Límite de Recursión en Entrevistas: - En Python, sys.getrecursionlimit() suele ser 1,000 llamadas. Para N > 1000, Python arroja RecursionError. Siempre que un problema pueda tener N = 100,000, la solución debe ser iterativa o simular la pila manualmente con un Vec en el Heap.
3. Pérdida de Punteros en Inversión de Listas: - Si alteras curr.next = prev antes de guardar la dirección del siguiente nodo original, pierdes irreversiblemente el resto de la lista. El uso de node.next.take() en Rust evita este error forzando el resguardo previo.

6. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

7. Puente a LeetCode y Práctica de Código#

1. LeetCode 206 — Reverse Linked List (Easy): - Implementa tanto la versión iterativa O(1) como la recursiva.
2. LeetCode 509 — Fibonacci Number (Easy): - Analiza el desastre exponencial de la recursión ingenua O(2^N) frente a la iterativa O(N).
3. LeetCode 234 — Palindrome Linked List (Easy): - Aplica la inversión de lista enlazada sobre la segunda mitad.

Navegación:

• ← Volver a Sesión 08: Memoria y Selection Sort
• Avanzar a Sesión 10: Runner Technique y Duplicados en Listas Enlazadas →