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

Independientemente del lenguaje de programación que utilices, a medida que comienzas a codificar más y más, aprendes conceptos que hacen que tu código sea conciso y fácil de leer/entender. Hay varios conceptos así en C también. Uno de ellos son las ‘funciones recursivas’, de las que hablaremos aquí 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 es llamada por la función en cuestión.

A continuación se muestra un ejemplo de recursión directa:

int func (int a)  
{  
    //declaraciones  
  
    func(a-1);  
  
    // declaraciones  
  
    return 0;  
}

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

int func (int a)  
{  
    //declaraciones  
  
    func_new(a);  
  
    // declaraciones  
  
    return 0;  
}  
  
int func_new(int b)  
{  
    //declaraciones  
  
    func(b-1);  
  
    //declaraciones  
  
    return 0;  
}

Como ya se mencionó al principio, la recursión te ayuda a lograr un código compacto, uno que no solo es fácil de escribir, sino también fácil de entender y revisar. Tomemos un ejemplo para hacer más claro este beneficio.

Estoy seguro de que todos ustedes han oído hablar del concepto de factorial. Para aquellos que no lo saben, el factorial es el resultado que obtienes cuando multiplicas un entero por todos los enteros positivos menores que él. Por ejemplo, el factorial de 5 es 5x4x3x2x1, que es igual a 120.

Aquí hay un código simple para encontrar el factorial de un número:

#include   
  
int main()  
{  
 int a = 0, i = 0, fact = 1;  
 printf("Ingresa un número: ");  
  
 scanf("%d", &a);  
   
 for(i=1; i<=a; i++)  
 {  
 fact = fact * i;  
   
 }  
 printf("El factorial del número es: %d ", fact);  
 return 0;  
}

Nota que este código es solo para que sepas cómo se puede calcular el factorial de un número a través de un programa en C. El programa no se ocupa de los casos extremos que pueden afectar la precisión del resultado que produce.

Así que esta es una de las muchas formas en que puedes calcular el factorial de un número sin usar una función recursiva. Ahora veamos un fragmento de código que utiliza recursión para calcular un factorial.

#include   
  
int factorial (int b)  
{  
 if(!b)  
 return 1;  
   
 return (b * factorial(b-1));  
}  
  
int main()  
{  
 int a = 0, fact = 1;  
 printf("Ingresa un número: ");  
  
 scanf("%d", &a);  
   
 fact = factorial(a);  
   
 printf("El factorial del número es: %d ", fact);  
 return 0;  
}

Así que 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 aquellos que no saben qué está pasando, el valor que el usuario ha ingresado, digamos 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 verificación para ver si el valor de entrada es cero, lo cual no es cierto cuando la función se llama por primera vez con el valor de entrada ‘5’.

Luego, 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 luego, nuevamente, estos pasos se repiten.

Así que si miras en términos generales, aquí es cómo se apilan estas llamadas de función:

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

Ahora, cuando factorial(0) se ejecuta, la condición ‘if’ en la función ‘factorial’ se vuelve verdadera, y se devuelve el valor ‘1’. Así que ahora, así es como se completan las llamadas listadas anteriormente (compara la última entrada en la lista anterior con la primera entrada en esta lista, y así sucesivamente):

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

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

Así que así es como funcionan las funciones recursivas. Si bien no hay duda sobre las ventajas de la función recursiva que hemos enumerado hasta ahora, también hay algunas desventajas.

Por ejemplo, en nuestro ejemplo anterior, hasta que la llamada ‘factorial(0)’ se completó, todas las llamadas ‘factorial’ anteriores estaban esperando a que se completara el procesamiento de la función. Sin mencionar el hecho de que las variables automáticas o locales ocupan memoria para cada llamada recursiva realizada.

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

Conclusión

Para concluir, aunque puede que no uses funciones recursivas con frecuencia en tus tareas de codificación diarias, es un concepto importante del que debes estar al tanto. Prueba el ejemplo que hemos mencionado aquí y ajústalo para entender aún mejor el concepto de funciones recursivas.