Introducción a la Recursividad

La sucesión de Fibonacci $F(n)$ para un entero $n \geq 0$ se define matemáticamente como:

Esta definición es recursiva porque el valor de la función para un caso $n > 1$ se expresa en términos de la misma función evaluada en instancias menores ($n-1$ y $n-2$). Los dos casos base garantizan que el desglose de llamadas finalice y retorne valores conocidos y definidos de manera directa.

La multiplicación $a \times b$ se puede definir de manera recursiva acumulando sumas del primer término $a$ y decrementando el segundo término $b$:

En cada paso recursivo se acumula $a$ y se reduce el multiplicador $b$ en una unidad, convergiendo linealmente hacia el caso base ($b = 0$).

La cantidad de dígitos $D(n)$ de un entero $n > 0$ se define de forma recursiva como:

Cada paso recursivo realiza la división entera por 10 (eliminando el último dígito del número) y suma 1 al contador acumulado, repitiendo el proceso hasta que el número sea menor que 10, donde se alcanza el caso base.

Versión Recursiva:

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

1
2
3
4
5
6
7
8
9
10
11
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
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;
}

Siguiendo las buenas prácticas, la cadena de entrada se declara como constante (const char *) según la regla 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 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
#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);
}

Para cumplir con las directivas de tipo, los índices se manejan con size_t (regla 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
#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);
}

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 Regla 0x2001h: Las funciones deben usar cláusulas de guarda y retornos anticipados para evitar 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
int sumar_hasta_cero_robusta(int n) {
    if (n <= 0) {
        return 0;
    }
    return n + sumar_hasta_cero_robusta(n - 1);
}

Para estimar el tamaño mínimo de un marco de pila en la arquitectura x86_64 bajo el estándar de llamada System V AMD64 ABI, se analiza cada componente del registro del marco:

1. Dirección de Retorno: Requiere 8 bytes para almacenar el puntero de instrucción del llamador.

2. Puntero de Marco Anterior (Saved Frame Pointer): Almacena el registro rbp previo, consumiendo 8 bytes.

3. Variables Locales: El arreglo long int variables_locales[4] ocupa $4 \times 8 \text{ bytes} = 32 \text{ bytes}$.

4. Parámetros de Entrada: El argumento int n (4 bytes) inicialmente se transfiere vía registro (edi). Sin embargo, el compilador debe respaldarlo en la pila para preservar su valor a lo largo de las activaciones sucesivas. Por cuestiones de alineación en arquitectura de 64 bits, este campo consume 8 bytes.

Sumando los componentes:

Bajo la convención x86_64 ABI, la pila debe estar alineada a límites de 16 bytes. Por lo tanto, el compilador redondea el tamaño de este marco a un múltiplo de 16, resultando en un tamaño real de 64 bytes por marco.

Para calcular el límite teórico de llamadas:

• El límite de la pila del sistema operativo es de $8 \text{ MB} = 8.388.608 \text{ bytes}$.

• Número máximo de marcos permitidos:

  $$\text{Profundidad Máxima} = \frac{8.388.608 \text{ bytes}}{64 \text{ bytes/marco}} = 131.072 \text{ llamadas}$$

  (8)

Un entero unsigned long long en C (64 bits) tiene un valor máximo representable de $2^{64} - 1 \approx 1.84 \times 10^{19}$.

1. Desbordamiento aritmético: El número de Fibonacci $F(93) = 12.200.160.415.121.876.738$ entra dentro del límite. Sin embargo, $F(94) = 19.740.274.219.868.223.167 > 2^{64}-1$, por lo cual el desbordamiento aritmético ocurre en $n = 94$.

2. Desbordamiento de pila (Stack Overflow): La profundidad máxima de la pila para la versión de Fibonacci con recursión doble $F(n) = F(n-1) + F(n-2)$ es lineal respecto de $n$ (la profundidad máxima es $n$). Para $n = 94$, la pila albergará como máximo 94 marcos activos simultáneamente en la rama más profunda, consumiendo menos de $6 \text{ KB}$ de memoria, lo cual es despreciable.

Por lo tanto, la implementación de Fibonacci fallará primero debido a un desbordamiento aritmético en $n = 94$ mucho antes de aproximarse a un stack overflow.