Tutorial de programación en C para Linux Parte 18: Funciones recursivas

Independientemente del lenguaje de programación que utilices, a medida que empiezas a codificar más y más, llegas a aprender conceptos que hacen que tu código sea nítido y fácil de leer/entender. También en el C hay varios conceptos de este tipo. Uno de ellos es el de «funciones recursivas», del que hablaremos en este artículo.

Una función recursiva es una función que se llama a sí misma. La llamada puede hacerse directamente desde el cuerpo de la función, o indirectamente desde alguna otra función que sea llamada por la función en cuestión.

A continuación tienes un ejemplo de recursión directa:

int func (int a)
{
    //statements

    func(a-1);

    // statements

    return 0;
}

Y aquí tienes un ejemplo de recursión indirecta:

int func (int a)
{
    //statements

    func_new(a);

    // statements

    return 0;
}

int func_new(int b)
{
    //statements

    func(b-1);

    //statementsur

    return 0;
}

Como ya hemos dicho al principio, la recursividad te ayuda a conseguir un código compacto, que no sólo es fácil de escribir, sino también de entender y revisar. Pongamos un ejemplo para que esta ventaja quede más clara.

Estoy seguro de que todos habréis oído hablar del concepto de factorial. Para los que no lo sepan, el factorial es el resultado que se obtiene al multiplicar un entero por todos los enteros positivos menores que él. Por ejemplo, el factorial de 5 es 5x4x3x2x1, que es igual a 120.

Aquí tienes un código sencillo para encontrar el factorial de un número:

#include <stdio.h>

int main()
{
 int a = 0, i = 0, fact = 1;
 printf("Enter a number: ");

 scanf("%d", &a);
 
 for(i=1; i<=a; i++)
 {
 fact = fact * i;
 
 }
 printf("Factorial of the number is: %d ", fact);
 return 0;
}

Ten en cuenta que este código es sólo para que sepas cómo se puede calcular el factorial de un número mediante un programa en C. El programa no tiene en cuenta los casos de esquina que pueden afectar a la precisión del resultado que produce.

Así que ésta es una de las muchas formas en que puedes calcular el factorial de un número sin utilizar una función recursiva. Veamos ahora un trozo de código que utiliza la recursión para calcular un factorial.

#include <stdio.h>

int factorial (int b)
{
 if(!b)
 return 1;
 
 return (b * factorial(b-1));
}

int main()
{
 int a = 0, fact = 1;
 printf("Enter a number: ");

 scanf("%d", &a);
 
 fact = factorial(a);
 
 printf("Factorial of the number is: %d ", fact);
 return 0;
}

Como puedes ver, la función «factorial» que realmente calcula el factorial es muy compacta. Y si prestas atención, también es muy fácil de entender.

Para los que no sepan lo que ocurre, el valor que el usuario ha introducido, por ejemplo 5, se pasa a la función «factorial» cuando se llama por primera vez desde la función «main». Dentro de la función «factorial», hay una comprobación para ver si el valor de entrada es cero, lo que no es cierto cuando se llama a la función por primera vez con el valor de entrada «5».

Entonces, la declaración de retorno contiene una expresión que multiplica 5 con el valor de retorno de ‘factorial(4)’. Así que ahora, la función ‘factorial’ se ejecuta una vez más, y llegamos a la siguiente expresión: return (4 * factorial(3)). Y de nuevo se repiten estos pasos.

Así que, si te fijas bien, así es como se apilan estas llamadas a la función

• 5 * factorial(4)
• 4 * factorial(3)
• 3 * factorial(2)
• 2 * factorial(1)
• 1 * factorial(0)

Ahora, cuando se ejecuta factorial(0), la condición «si» de la función «factorial» se hace verdadera, y se devuelve el valor «1». Así es como se completan las llamadas de la lista anterior (compara la última entrada de la lista anterior con la primera entrada de esta lista, y así sucesivamente):

• 1 * 1
• 2 * (1*1)
• 3 * (2*(1*1))
• 4 * (3*(2*(1*1)))
• 5 * (4 * (3*(2*(1*1))))

Lo cual es efectivamente 5 * 4 *3 * 2 * 1, que a su vez es 120, el factorial de 5.

Así es como funcionan las funciones recursivas. Aunque no hay duda de las ventajas de las funciones recursivas que hemos enumerado hasta ahora, también hay algunos inconvenientes.

Por ejemplo, en nuestro ejemplo anterior, hasta que se completó la llamada «factorial(0)», todas las llamadas anteriores a «factorial» estaban esperando a que se completara el procesamiento de la función. Por no hablar del hecho de que las variables automáticas o locales ocupan memoria por cada llamada recursiva realizada.

Así que, efectivamente, no se ahorra espacio de almacenamiento cuando se utiliza la recursión. Además, tampoco hay garantía de que tu código sea más rápido en la ejecución. La verdadera ventaja de una función recursiva es cuando tratas con estructuras de datos, de las que hablaremos más adelante como parte de esta serie de tutoriales de C en curso.

Conclusión

Para concluir, aunque no utilices la función recursiva con frecuencia en tus tareas de codificación cotidianas, es un concepto importante que debes conocer. Prueba el ejemplo que hemos mencionado aquí, y modifícalo para comprender mejor el concepto de las funciones recursivas.