Recursividad en C: del caso base al factorial paso a paso

La recursividad consiste en resolver un problema mediante versiones más pequeñas del mismo problema. En C, una función puede llamarse a sí misma: cada llamada conserva sus parámetros y variables automáticas mientras espera el resultado de la siguiente. Para utilizar esta técnica correctamente, necesitas un caso base, una reducción que conduzca hasta él y una profundidad de llamadas compatible con la pila disponible. [2], [1]

1. Tres ideas para entender una función recursiva

1. Resolver algo más pequeño: la llamada recursiva debe abordar una instancia reducida del mismo problema, no repetir indefinidamente la tarea original. [2]
2. Detenerse explícitamente: el caso base proporciona una respuesta sin realizar otra llamada recursiva. [2]
3. Recordar lo pendiente: cada llamada mantiene sus propios parámetros y variables automáticas; las llamadas anidadas están limitadas por el tamaño de la pila. [1]

La pregunta útil al diseñar una función recursiva no es simplemente «¿cómo hago que se llame a sí misma?», sino «¿qué parte puedo resolver si ya conozco la respuesta de un problema menor?». Esa distinción transforma una repetición en una descomposición. También permite revisar el algoritmo antes de escribirlo: identifica qué dato disminuye y qué valor permite responder directamente. Tener una condición de parada escrita no basta si las llamadas nunca llegan a ella. La reducción y el caso base deben funcionar juntos. [2]

2. Un ejemplo clásico: calcular el factorial

El factorial permite observar el mecanismo sin mezclarlo con otras estructuras. Como ejemplo didáctico, definimos el factorial de cero como uno y, para un entero positivo, multiplicamos ese entero por el factorial de su anterior. Así, el problema «calcular el factorial de 4» se reduce a «calcular el factorial de 3» y conservar una multiplicación pendiente. El siguiente código es una elaboración ilustrativa del patrón, no una reproducción del ejemplo documental. Para mantener delimitado el ejercicio, su precondición es recibir un entero entre 0 y 5. [1], [2]

/* Precondicion del ejemplo: 0 <= n && n <= 5. */
unsigned int factorial(unsigned int n)
{
    if (n == 0)
        return 1;

    return n * factorial(n - 1);
}

Para la entrada 4, la expansión conceptual es: factorial(4) = 4 × factorial(3), después 4 × 3 × factorial(2), y finalmente 4 × 3 × 2 × 1 × factorial(0). El caso base devuelve 1. A partir de ahí se completan las operaciones pendientes: factorial(1) devuelve 1; factorial(2), 2; factorial(3), 6; y factorial(4), 24. Hay dos momentos distintos: descender reduciendo el argumento y regresar completando los resultados. La función no necesita que todas las multiplicaciones estén resueltas antes de efectuar la siguiente llamada. [1], [2]

La revisión decisiva consiste en comprobar qué sucede antes de calcular n − 1. En este ejemplo, cuando n vale cero, la función devuelve inmediatamente; por tanto, esa llamada no ejecuta la reducción. Para las entradas positivas del dominio elegido, restar uno acerca el argumento al caso base. Esta comprobación relaciona la condición de parada con el recorrido real del algoritmo, en lugar de tratarlas como dos elementos independientes. [2]

3. Qué conserva cada llamada en C

En la documentación de C de Microsoft, cada llamada obtiene nuevo almacenamiento para sus parámetros y sus variables auto y register. Por eso, cuando factorial(4) llama a factorial(3), el argumento de la primera llamada no se convierte en 3: cada instancia conserva el suyo. Los parámetros de una instancia tampoco son directamente accesibles como parámetros de otra. Esta separación explica cómo una llamada puede esperar y después continuar usando el valor que tenía antes de invocar a la siguiente. [1]

Las variables declaradas static son una excepción importante: no reciben almacenamiento nuevo en cada llamada, sino que todas las referencias acceden a una misma zona que existe durante la vida del programa. Por ello, si quieres guardar un dato independiente para cada nivel recursivo, no debes suponer que una variable static cumple esa función. En el ejemplo, mantener el argumento como parámetro hace explícita la separación entre niveles; introducir estado compartido exigiría razonar también sobre cómo lo modifica cada llamada. [1]

4. Recursividad e iteración: distinguir expresión y coste

Una solución recursiva no es obligatoria por el hecho de que el problema admita una definición recursiva. Los bucles while y for ofrecen otra forma de expresar trabajo repetido, y una función recursiva puede transformarse en una solución iterativa con una pila. La comparación útil consiste en preguntar qué estado queda pendiente y dónde se conserva. La tabla resume criterios de diseño, no resultados de una prueba de rendimiento ni una clasificación de superioridad. [2], [1]

5. De la reducción simple a divide y vencerás

El factorial ilustra una cadena: cada llamada genera un único problema menor. La idea más amplia es descomponer un problema en subproblemas del mismo tipo, estrategia que la referencia enciclopédica relaciona con divide y vencerás. La conexión importante no es que toda función recursiva haga exactamente lo mismo, sino que una solución puede construirse a partir de soluciones menores. Para analizarla, conviene distinguir qué trabajo resuelve cada llamada, qué delega y qué respuesta necesita recibir para completar su parte. [1], [2]

Antes de utilizar recursividad, comprueba tres cosas: que el caso base responde correctamente, que cada camino recursivo se acerca a él y que la cantidad de llamadas simultáneas resulta razonable. La documentación de Microsoft advierte que el tamaño de la pila limita las llamadas recursivas. Por tanto, terminar matemáticamente y poder ejecutarse con los recursos disponibles son cuestiones distintas. No hay aquí una profundidad universal ni una medición que permita afirmar que una implementación será más rápida: la decisión debe considerar el algoritmo concreto y su entorno. [1], [2]

Explore next

1. ¿Cómo convertir el factorial recursivo en una función iterativa en C?
2. ¿Cómo demostrar que una función recursiva alcanza siempre su caso base?
3. ¿Qué cambia al utilizar variables static dentro de una función recursiva?
4. ¿Cómo representar las llamadas pendientes mediante una pila explícita?

Sources

Open a source or expand its cited passages.

Relevance scores are model estimates of how well each source addresses this question, not probabilities or fact-check ratings. Reasoned guidance is identified on hover.

1. 94Funciones recursivas | Microsoft Learnlearn.microsoft.comDocumentación primaria pertinente para las llamadas y el almacenamiento en C; el ejemplo de factorial contiene una condición que no sirve como modelo completo de terminación.›
2. 85Recursión (ciencias de computación) - Wikipedia, la enciclopedia librees.wikipedia.orgExplica reducción, caso base e iteración; sus observaciones generales de eficiencia no sustituyen mediciones de un algoritmo concreto.›