Introducción a la Recursividad - Programación 1

Introducción a la recursividad¶

Prerrequisitos: funciones, condicionales, parámetros por valor y stack frame. Debés poder trazar una llamada y reconocer cuándo una variable local deja de existir.
Objetivo: diseñar un caso base alcanzable y demostrar que cada llamada se acerca a él.
Comprobación de salida: señalá el caso base y la medida que decrece en una función recursiva propuesta.

Introducción¶

La recursividad es una técnica de programación fundamental en la que una función se llama a sí misma para resolver un problema. Este enfoque se basa en la idea de descomponer un problema complejo en subproblemas más pequeños y de la misma naturaleza.

Desarrollo¶

Definición Matemática¶

Desde una perspectiva matemática, una definición recursiva tiene dos partes esenciales:

Caso Base: Es una o más condiciones terminales que no requieren de una nueva llamada a la función para ser resueltas. Es la solución explícita para el caso más simple del problema.
Paso Recursivo (o Relación de Recurrencia): Es la regla que reduce el problema a una versión más simple de sí mismo. Define cómo se resuelve el problema para un caso n en términos de uno o más casos “menores” (por ejemplo, n-1).

Un ejemplo clásico es la función factorial, $n!$ , que se define de la siguiente manera:

n! = \begin{cases} 1 & \text{si } n = 0 \text{ (Caso Base)} \\ n \times (n-1)! & \text{si } n > 0 \text{ (Paso Recursivo)} \end{cases}

(1)

Esta definición establece que el factorial de 0 es 1 (caso base) y que el factorial de cualquier otro número natural n es n multiplicado por el factorial de n-1.

Construcción de Algoritmos Recursivos en C¶

Para implementar un algoritmo recursivo en C, debés seguir la estructura de la definición matemática.

Componentes Clave¶

Un algoritmo recursivo siempre debe tener:

Caso Base: Una estructura condicional (normalmente un if) que verifica si se ha alcanzado la condición de parada. Sin un caso base, la función se llamaría a sí misma infinitamente, resultando en un error de desbordamiento de pila (stack overflow).
Paso Recursivo: La parte del código donde la función se invoca a sí misma, pero con argumentos que la acercan progresivamente al caso base. Es crucial que cada llamada recursiva opere sobre un subproblema más pequeño.

Ejemplo: Función Factorial en C¶

Veamos cómo se traduce la definición matemática del factorial a una función en C.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
// Declaración de la función factorial
long int factorial(int n);
int main(void)
{
    int numero = 5;
    long int resultado = factorial(numero);
    if (resultado == -1)
    {
        printf("Error: no se puede calcular el factorial de un número
        negativo.\n");
    }
    else
    {
        printf("El factorial de %d es %ld\n", numero, resultado);
    }
    return 0;
}
// Definición de la función recursiva
long int factorial(int n)
{
    // Validación de precondición (robustez ante valores inválidos, regla
    {
        ref
    }`0x2001h`)
    if (n < 0)
    {
        return -1;
    }
    // Caso Base: si n es 0, el factorial es 1.
    if (n == 0)
    {
        return 1;
    }
    // Paso Recursivo: n * factorial(n-1)
    return n * factorial(n - 1);
}

Análisis del Código¶

Caso Base: La línea if (n == 0) comprueba la condición de parada. Si n es 0, la función retorna 1 y la cadena de llamadas recursivas comienza a resolverse.
Paso Recursivo: En la última sentencia, la función retorna el resultado de n multiplicado por el valor devuelto por la llamada a factorial(n - 1). Esta llamada opera sobre un subproblema de menor tamaño (n-1), garantizando la convergencia hacia el caso base.

Pila de llamadas (Call Stack) y Anatomía del Stack Frame

Cada vez que un programa invoca una función, se reserva un espacio de memoria física en la pila del sistema (call stack) denominado marco de pila o stack frame. En una arquitectura moderna típica (como x86_64), un marco de pila contiene los siguientes elementos esenciales:

Dirección de Retorno: La dirección de la instrucción en la función llamadora a la que debe retornar el control del flujo del procesador una vez que finalice la ejecución de la función actual.
Parámetros de Entrada: Los argumentos provistos a la función.
Puntero de Marco Anterior (Saved Frame Pointer): La dirección de base (rbp) del marco de la función que la invocó.
Variables Locales: Espacio reservado para almacenar los datos definidos internamente en la función durante su ciclo de vida.

En la recursividad, cada llamada consecutiva apila un nuevo marco. Estos marcos se acumulan hasta alcanzar el caso base, punto en el cual se inicia la fase de resolución y retorno (“desapilado”) en orden inverso al de la llamada (LIFO: Last In, First Out).

A continuación se muestra de forma gráfica y formal la distribución física en memoria del Call Stack durante el cálculo recursivo de factorial(3) hasta alcanzar el caso base, ilustrando las direcciones físicas de memoria en la pila y las direcciones lógicas de retorno de código:

Crecimiento y colapso de los marcos de pila en la recursión de factorial(3).
Cada llamada apila un nuevo marco temporal consumiendo espacio físico de memoria
RAM. — Figure 1:Crecimiento y colapso de los marcos de pila en la recursión de `factorial(3)`. Cada llamada apila un nuevo marco temporal consumiendo espacio físico de memoria RAM.

Como se observa en el diagrama, cada llamada suspendida (factorial(3) y factorial(2)) mantiene su estado completo en una dirección de memoria diferente de la RAM. Solo cuando factorial(1) retorna su valor constante 1 a la dirección de retorno de su llamador, el marco superior se destruye (se desplaza el puntero de pila rsp) y se reanuda la evaluación aritmética en el marco inmediatamente inferior.

El Peligro de la Recursividad: Stack Overflow y la Paradoja del Factorial¶

El tamaño total disponible para la pila de llamadas (call stack) es finito (típicamente entre 1 y 8 megabytes en sistemas Unix/Linux). Si el consumo de pila excede dicho límite físico, se produce un desbordamiento catastrófico de pila o stack overflow, lo cual interrumpe inmediatamente el programa con un fallo de segmentación.

Las causas principales de este fallo son:

Ausencia o fallo en el Caso Base (Recursión Infinita): Si la condición de parada no se cumple o los parámetros no convergen al caso base.
Recursión Demasiado Profunda: Aún si el algoritmo es lógicamente correcto, si la profundidad de llamadas es excesiva, la pila se agotará.

La Paradoja del Factorial: Límites del Tipo de Dato vs. Límites de la Pila¶

Contraste Cuantitativo

El factorial es el ejemplo introductorio por excelencia de la recursividad, pero presenta una severa deficiencia didáctica si se analiza con rigor de ingeniería de software.

En sistemas de 64 bits modernos, un entero de tipo long int de C ocupa 8 bytes, permitiendo almacenar valores en el rango:

-2^{63} \leq \text{long int} \leq 2^{63} - 1 \quad (\approx 9.22 \times 10^{18})

(2)

El factorial de 20 es $20! \approx 2.43 \times 10^{18}$ (entra dentro de los límites del tipo).
El factorial de 21 es $21! \approx 5.10 \times 10^{19}$ (supera la capacidad máxima del tipo long int y produce un desbordamiento aritmético).

Por lo tanto, la implementación de factorial(n) recursiva en C fallará y devolverá valores matemáticamente erróneos para $n \geq 21$ . Sin embargo, para provocar un stack overflow físico en una pila de 8 MB con marcos de 32 bytes, se requerirían aproximadamente:

\frac{8 \times 10^6 \text{ bytes}}{32 \text{ bytes/marco}} \approx 250.000 \text{ llamadas recursivas}

(3)

Esto significa que el desbordamiento aritmético ocurre en $n=21$ , mucho antes de comprometer la estabilidad física del stack. El estudiante no ve el límite del stack en este ejemplo clásico, sino el límite físico de almacenamiento del tipo de dato binario.

Ejercicios de Autoevaluación¶

Definición Matemática¶

Construcción de Algoritmos en C¶

Solution to Exercise 4

Versión Recursiva:

Aplica la regla de robustez 0x2001h: Las funciones deben usar cláusulas de guarda y retornos anticipados para reducir la anidación profunda para validar precondiciones y el uso de llaves:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
double potencia_recursiva(double a, int b)
{
    if (b < 0)
    {
        return -1.0;
    }
    // Caso Base
    if (b == 0)
    {
        return 1.0;
    }
    // Paso Recursivo
    return a * potencia_recursiva(a, b - 1);
}

Versión Iterativa (con lazo for):

1
2
3
4
5
6
7
8
9
10
11
12
13
double potencia_iterativa(double a, int b)
{
    if (b < 0)
    {
        return -1.0;
    }
    double resultado = 1.0;
    for (int i = 0; i < b; i++)
    {
        resultado *= a;
    }
    return resultado;
}

Solution to Exercise 5

Siguiendo las buenas prácticas, la cadena de entrada se declara como constante (const char *) según la regla 0x3007h: Los argumentos de tipo puntero deben ser const siempre que la función no los modifique y se retorna el tipo size_t de acuerdo a la regla 0x3010h: Las variables que representan tamaños o índices de arreglos deben ser de tipo size_t:

1
2
3
4
5
6
7
8
9
10
#include <stddef.h>
size_t contar_caracter(const char *cadena, char c)
{
    if (*cadena == '\0')
    {
        return 0;
    }
    size_t coincide = (*cadena == c) ? 1 : 0;
    return coincide + contar_caracter(cadena + 1, c);
}

Solution to Exercise 6

Para cumplir con las directivas de tipo, los índices se manejan con size_t (regla 0x3010h: Las variables que representan tamaños o índices de arreglos deben ser de tipo size_t):

1
2
3
4
5
6
7
8
9
10
11
12
#include <stddef.h>
void invertir_arreglo(int arr[], size_t ini, size_t fin)
{
    if (ini >= fin)
    {
        return;
    }
    int aux = arr[ini];
    arr[ini] = arr[fin];
    arr[fin] = aux;
    invertir_arreglo(arr, ini + 1, fin - 1);
}

Diagnóstico y Estabilidad¶

Exercise 7

Analizá la siguiente función recursiva en C y determiná por qué se produce un error de desbordamiento de pila (stack overflow) para ciertos valores de entrada enteros. ¿Cuál es el error en la condición de parada (caso base)?

1
2
3
4
5
6
7
8
int sumar_hasta_cero(int n)
{
    if (n == 0)
    {
        return 0;
    }
    return n + sumar_hasta_cero(n - 1);
}

Solution to Exercise 7

El error reside en que la condición de parada if (n == 0) solo se alcanza si el argumento inicial n es un entero no negativo. Si la función se invoca con un valor negativo (por ejemplo, sumar_hasta_cero(-1)), la llamada recursiva realiza n - 1, decrementando el valor hacia $-\infty$ (-2, -3, -4, etc.). Como nunca se cumple la condición n == 0, la función continúa apilando marcos de pila en el Call Stack de forma infinita hasta agotar el límite físico de memoria del stack, provocando un stack overflow.

Para resolver esta vulnerabilidad de parada, de acuerdo a la regla de robustez 0x2001h: Las funciones deben usar cláusulas de guarda y retornos anticipados para reducir la anidación profunda, la guarda del caso base debe generalizarse para cubrir todos los números menores o iguales a cero:

1
2
3
4
5
6
7
8
int sumar_hasta_cero_robusta(int n)
{
    if (n <= 0)
    {
        return 0;
    }
    return n + sumar_hasta_cero_robusta(n - 1);
}

Exercise 8

Considerando la siguiente función recursiva en C:

1
2
3
4
5
6
7
8
9
10
long int calcular_suma_recursiva(int n)
{
    long int variables_locales[4] = {0};
    if (n <= 0)
    {
        return 0;
    }
    variables_locales[0] = n;
    return variables_locales[0] + calcular_suma_recursiva(n - 1);
}

Estimá el tamaño mínimo teórico de su marco de pila (stack frame) en una arquitectura típica de 64 bits (donde sizeof(int) == 4 y sizeof(long int) == 8), asumiendo que el compilador no realiza optimizaciones de llamada de cola. Estimá la profundidad de recursión teórica y el número máximo de llamadas antes de producir un desbordamiento físico de la pila (stack overflow) si el límite de la pila del sistema operativo es de $8 \text{ MB}$ .

Glosario¶

Recursión: Técnica de programación y diseño algorítmico donde una función se define e invoca en términos de sí misma.
Caso base: Condición lógica terminal en un algoritmo recursivo que detiene la recursión y retorna un resultado de forma directa sin realizar nuevas llamadas.
Paso recursivo: Sentencia lógica en una función recursiva donde se realiza una nueva invocación a la propia función sobre un subproblema de menor tamaño.
Stack Overflow: Desbordamiento físico de la pila de llamadas del sistema provocado por el consumo excesivo de memoria física asignada al stack.
Desbordamiento aritmético: Situación física en la cual el resultado numérico de una operación excede los límites representables por el tipo de dato físico de la variable.

Síntesis y Resumen¶

En este capítulo analizaste los principios de la recursión y su comportamiento en memoria:

Estructuración recursiva: Todo algoritmo recursivo requiere al menos de un caso base (para detener la ejecución) y un paso recursivo que reduzca el problema de forma convergente.
Funcionamiento en hardware: Cada invocación apila un marco de pila (stack frame) con su propia copia de parámetros y variables locales automáticas en el Call Stack.
Riesgos y límites: La recursión mal controlada o excesivamente profunda provoca fallas de segmentación (stack overflow). Sin embargo, en ciertos algoritmos el desbordamiento numérico del tipo de dato se alcanza mucho antes de saturar físicamente la pila.

Referencias y Lecturas Complementarias¶

Roberts, E. (2006). Thinking Recursively in C. Wiley.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Chapter 4: Divide-and-Conquer.
ISO/IEC 9899 Language Standard Section 6.5.2.2: Function calls.