C++

9.8. 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. Esto, programando, se haría:

// Introducción a C++, Nacho Cabanes
// Ejemplo 09.14:
// Funciones recursivas: factorial
 
#include <iostream>
using namespace std;
 
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;
    cout << "Introduzca un número entero: ";
    cin >> num;
    cout << "Su factorial es: " << fact(num) << endl;
 
    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:

• (9.8.1) 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 = 53 = 5 ·5 · 5 = 125). Esta función se debe crear de forma recursiva.
• (9.8.2) 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".
• (9.8.3) 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).
• (9.8.4) Crear un programa que emplee recursividad para calcular la suma de los elementos de un vector.
• (9.8.5) Crear un programa que emplee recursividad para calcular el mayor de los elementos de un vector.
• (9.8.6) Crear un programa que emplee recursividad para dar la vuelta a una cadena de caracteres (por ejemplo, a partir de "Hola" devolvería "aloH").
• (9.8.7) 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.
• (9.8.8) 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).