7.10. Recursividad

Una función recursiva es aquella que se define a partir de ella misma. Dentro de las matemáticas tenemos varios ejemplos. Uno clásico es el "factorial de un número":

n! = n · (n-1) · (n-2) · ... · 3 · 2 · 1

(por ejemplo, el factorial de 4 es 4 · 3 · 2 · 1 = 24)

Si pensamos que el factorial de n-1 es

(n-1)! = (n-1) · (n-2) · (n-3) · ... · 3 · 2 · 1

Entonces podemos escribir el factorial de un número a partir del factorial del siguiente número:

n! = n · (n-1)!

Esta es la definición recursiva del factorial, ni más ni menos. Esto, programando, se haría:

/*---------------------------*/
/*  Ejemplo en C nº 70:      */
/*  C070.C                   */
/*                           */
/*  Funciones recursivas:    */
/*  factorial                */
/*                           */
/*  Curso de C,              */
/*    Nacho Cabanes          */
/*---------------------------*/

#include 

long fact(int n) {
  if (n==1)               /* Aseguramos que termine */
    return 1;
  return n * fact (n-1);  /* Si no es 1, sigue la recursión */
}

int main() {
  int num;
  printf("Introduzca un número entero: ");
  scanf("%d", &num);
  printf("Su factorial es: %ld\n", fact(num));
  
  return 0;
}

Dos consideraciones importantes:

• Atención a la primera parte de la función recursiva: es MUY IMPORTANTE comprobar que hay salida de la función, para que nuestro programa no se quede dando vueltas todo el tiempo y deje el ordenador (o la tarea actual) "colgado".
• Los factoriales crecen rápidamente, así que no conviene poner números grandes: el factorial de 16 es 2.004.189.184, luego a partir de 17 podemos obtener resultados erróneos, según sea el tamaño de los números enteros en nuestro sistema.

¿Qué utilidad tiene esto? Pues más de la que parece: muchos problemas complicados se pueden expresar a partir de otro más sencillo. En muchos de esos casos, ese problema se podrá expresar de forma recursiva. Más adelante veremos algún otro ejemplo.

Ejercicios propuestos:

• Crear una función que calcule el valor de elevar un número entero a otro número entero (por ejemplo, 5 elevado a 3 = 5³ = 5 ·5 · 5 = 125). Esta función se debe crear de forma recursiva.
• Como alternativa, crear una función que calcule el valor de elevar un número entero a otro número entero de forma NO recursiva (lo que llamaremos "de forma iterativa"), usando la orden "for".
• Crear un programa que emplee recursividad para calcular un número de la serie Fibonacci (en la que los dos primeros elementos valen 1, y para los restantes, cada elemento es la suma de los dos anteriores).
• Crear un programa que emplee recursividad para calcular la suma de los elementos de un vector.
• Crear un programa que emplee recursividad para calcular el mayor de los elementos de un vector.
• Crear un programa que emplee recursividad para dar la vuelta a una cadena de caracteres (por ejemplo, a partir de "Hola" devolvería "aloH").
• Crear, tanto de forma recursiva como de forma iterativa, una función diga si una cadena de caracteres es simétrica (un palíndromo). Por ejemplo, "DABALEARROZALAZORRAELABAD" es un palíndromo.
• Crear un programa que encuentre el máximo común divisor de dos números usando el algoritmo de Euclides : Dados dos números enteros positivos m y n, tal que m > n, para encontrar su máximo común divisor, es decir, el mayor entero positivo que divide a ambos: - Dividir m por n para obtener el resto r (0 = r < n) ; - Si r = 0, el MCD es n.; - Si no, el máximo común divisor es MCD(n,r).