Regla 0x2017h: Toda funcion recursiva debe tener un caso base explicito - Programación 1

0x2017h: Toda funcion recursiva debe tener un caso base explicito¶

Enunciado normativo¶

Toda funcion recursiva DEBE declarar un caso base explicito y alcanzable que detenga la recursion.

Síntoma en el código del estudiante¶

Una función que se invoca a sí misma sin ninguna condición que detenga la cadena, o con una condición que nunca se alcanza porque el argumento no avanza hacia ella. El programa compila sin errores y aborta en ejecución con SIGSEGV.

Diagnóstico¶

Mecanismo del defecto¶

Cada llamada a una función reserva un marco de activación en la pila con sus parámetros y su dirección de retorno. Sin un caso base, la función se llama indefinidamente y la pila crece hasta agotar el espacio reservado por el sistema. En ese momento el proceso recibe una violación de segmento. El return que “debería” cortar nunca se alcanza porque falta la guarda que lo proteja, o porque el argumento no decrece.

Esto conecta con el uso correcto de funciones que exige 0x2008h: Los ejercicios deben ser resueltos mediante funciones: una función debe tener un contrato completo, y su caso base es parte de él.

Consecuencia observable¶

El depurador muestra una pila de miles de marcos idénticos apilados. El sistema reporta Segmentation fault (core dumped), y la regla 0x2008h: Los ejercicios deben ser resueltos mediante funciones se complementa con 0x2001h: Las funciones deben usar cláusulas de guarda y retornos anticipados para reducir la anidación profunda (la guarda de entrada es el caso base).

Fundamento en el estándar C11¶

El estándar no fija un tamaño de pila; deja esa implementación al entorno (§5.2.4.1 enumera los límites mínimos de traducción, no de ejecución). Por eso la recursión sin corte no es un error de compilación sino un defecto de ejecución con comportamiento indefinido de facto: el proceso termina de forma anormal. La norma exige que cada llamada retorne para que el flujo sea predecible (§6.9.1).

Corrección idiomática¶

❌ Código con el antipatrón¶

void cuenta(int n)
{
    cuenta(n - 1);
}

✅ Código refactorizado¶

void cuenta(int n)
{
    if (n <= 0) {
        return;
    }

    cuenta(n - 1);
}

La guarda inicial corta la recursión y el argumento avanza hacia el caso base.

Errores típicos al compilar o ejecutar¶

$ ./programa
Segmentation fault (core dumped)

$ gdb ./programa
#0  cuenta (n=-31234) at cuenta.c:4
#1  cuenta (n=-31233) at cuenta.c:4
#2  cuenta (n=-31232) at cuenta.c:4
... miles de marcos idénticos ...

Checklist de verificación¶

¿Toda función recursiva tiene un caso base explícito?
¿El argumento avanza hacia ese caso base en cada llamada?
¿El caso base se evalúa antes de la llamada recursiva?
¿Probé con el valor extremo que debería cortar (0, NULL, lista vacía)?

Reglas relacionadas¶

0x2008h: Los ejercicios deben ser resueltos mediante funciones — regla que norma este defecto: resolver con funciones bien formadas.
0x2001h: Las funciones deben usar cláusulas de guarda y retornos anticipados para reducir la anidación profunda — la guarda de entrada es, en recursión, el caso base.
0x2003h: Todas las funciones deben incluir documentación completa y estructurada — el contrato documenta la precondición y la terminación.
0x2010h: Prohibición de reasignar o modificar parámetros recibidos por valor dentro de la función — no reasignar el parámetro evita perder la condición de corte.

Síntoma en el código del estudiante¶

Dos o más funciones que se llaman entre sí en ciclo, sin que ninguna incluya una condición de corte. El programa compila y falla en ejecución con Segmentation fault.

Diagnóstico¶

Mecanismo del defecto¶

La recursión mutua reparte el estado entre varias funciones, de modo que la condición de corte debe vivir en al menos una de ellas. Si el estudiante “traduce” el ciclo de llamadas sin escribir el caso base, la pila acumula marcos de fa y fb alternados hasta agotarse. El error es especialmente difícil de ver porque ninguna función es recursiva por sí sola: el ciclo aparece recién en el grafo de llamadas.

Modificar un parámetro por valor dentro del ciclo (por ejemplo n--) agrava el problema, porque oculta que el argumento no se está pasando hacia el corte. La regla 0x2010h: Prohibición de reasignar o modificar parámetros recibidos por valor dentro de la función exige conservar el parámetro y pasar la expresión modificada; combinada con la guarda de 0x2001h: Las funciones deben usar cláusulas de guarda y retornos anticipados para reducir la anidación profunda, da una recursión terminante.

Consecuencia observable¶

El depurador muestra marcos alternados de las dos funciones. El sistema reporta Segmentation fault (core dumped), y el análisis del grafo de llamadas detecta el ciclo.

Fundamento en el estándar C11¶

La pila de ejecución y su tamaño son responsabilidad de la implementación (§5.2.4.1 fija límites mínimos de traducción, no de ejecución). Una recursión sin corte consume el recurso hasta la falla. El estándar garantiza el retorno de cada llamada (§6.9.1); sin caso base, ese retorno no ocurre y el programa termina de forma anormal.

Corrección idiomática¶

❌ Código con el antipatrón¶

void fa(int n) { fb(n); }
void fb(int n) { fa(n); }

✅ Código refactorizado¶

void fb(int n);

void fa(int n)
{
    if (n <= 0) {
        return;
    }

    fb(n - 1);
}

void fb(int n)
{
    if (n <= 0) {
        return;
    }

    fa(n - 1);
}

Cada función del ciclo tiene su caso base y delega con un argumento que avanza hacia él, de modo que la profundidad de la pila queda acotada por n.

Errores típicos al compilar o ejecutar¶

$ ./programa
Segmentation fault (core dumped)

$ gdb ./programa
#0  fa (n=-99999) at ciclo.c:2
#1  fb (n=-99998) at ciclo.c:3
#2  fa (n=-99999) at ciclo.c:2
... marcos alternados hasta agotar la pila ...

Checklist de verificación¶

¿Cada función del ciclo tiene su caso base?
¿El argumento avanza hacia el corte en cada salto?
¿Reasigné algún parámetro por valor en vez de pasar la expresión?
¿El grafo de llamadas no contiene ciclos sin salida?

Reglas relacionadas¶

0x2010h: Prohibición de reasignar o modificar parámetros recibidos por valor dentro de la función — regla que norma este defecto: no reasignar parámetros por valor.
0x2008h: Los ejercicios deben ser resueltos mediante funciones — resolver con funciones implica darles un contrato completo.
0x2001h: Las funciones deben usar cláusulas de guarda y retornos anticipados para reducir la anidación profunda — la guarda inicial es el caso base de la recursión.
0x2003h: Todas las funciones deben incluir documentación completa y estructurada — documentar la precondición y la terminación de cada función.