38. C++ || Funciones recursividad

Una función recursiva es aquella que se llama a sí misma. Sabemos que este concepto a primeras no es fácil de comprender, por eso lo vamos a tratar de explicar lo mejor posible.

Está la recursividad o recursión directa, que es el proceso por el cual una función se llama a sí misma desde el propio cuerpo de la función. También está la recursividad o recursión indirecta, la cual implica más de una función.

Para dar un ejemplo de la recursividad indirecta piensa en la función main(), esta por su parte llama a una función que se llama funcionUno(), a continuación, funcionUno() llama a otra función con el nombre de funcionDos(). Ahora, en algún punto del programa, funcionDos() llama a funcionUno(), esto sería una segunda llamada de funcionUno(). A esto se le conoce como recursión indirecta, pero recursiva, ya que funcionUno() ha sido llamada dos veces sin retornar ningún valor.

Para dar un ejemplo de la recursividad directa, pensaremos en el factorial de un número, en este curso hemos visto diferentes maneras de resolver este problema, pero hay más, incluso una forma más eficiente.

Sabemos que el factorial de un número n es igual a:

n! = n * (n - 1) * (n – 2) * . . . * 3 * 2 * 1

¿Qué queremos decir con esto? Que si pensamos en el factorial de 5, debemos saber que eso es:

5! = 5 * 4 *3 * 2 * 1

o lo que es igual a:

5! = 5 * (5 – 1) * (5 – 2) * (5 - 3) * (5 -4)

Con esto podemos concluir que, si queremos sacar el factorial de 5, debemos saber cuánto es el factorial de 4, y para sacar el factorial de 4, debemos a su vez, saber cuánto es el factorial de 3 y así sucesivamente hasta tener que saber cuánto es el factorial de 1, que por supuesto, es 1.

Entonces podríamos pensar en lo siguiente:

5! = 5 * 4!

4! = 4 * 3!

3! = 3 * 2!

2! = 2 * 1!

1! = 1

Entonces, ya que sabemos cuánto es el factorial de 1

2! = 2 * 1! = 2 * 1 = 2

3! = 3 * 2! = 3 * 2 = 6

4! = 4 * 3! = 4 * 6 = 24

5! = 5 * 4! = 5 * 24 = 120

Y exactamente esto es una función recursiva, y su implementación sería la siguiente:

#include &ltiostream&gt
using namespace std;

double factorial(int numero);

int main(){
    int numero;
    cout &lt&lt "Introduzca numero: ";
    cin &gt&gt numero;
    cout &lt&lt "factorial: " &lt&lt factorial(numero) &lt&lt endl;

    return 0;
}

double factorial(int numero){
    if (numero == 1){
        return 1;
    }else{
        return numero*factorial(numero-1);
    }
}

Es un poco enredado y te puedes estar preguntando, qué pasa en esa función, lo explicamos paso a paso.

Se llama la función factorial() desde el main(), en la función, entra como parámetro un número entero (int) y hay una condición, si ese número es igual a 1, entonces la función va a retornar el valor de 1.

if (numero == 1){
return 1;
}

¿Pero qué ocurre si ese valor es mayor a 1? Entonces entra en el bloque else y como pueden notar, en ese bloque se llama nuevamente a la misma función y de parámetro se envía el mismo número pero restandole 1.

else{
return (numero*factorial(numero-1));
}

Vamos a simular el proceso con el número 4. Supongamos que ese es el número que enviamos desde la función principal. El número 4 entra en la función factorial y se evalúa la condición

¿El número es igual a 1? Por supuesto que no. Pasamos al bloque else, entonces la función va a retornar el mismo número multiplicado por factorial(numero – 1), el parámetro (numero – 1) es igual a 3, entonces quedaría:

return 4 * factorial(3);

Como se ha llamado de nuevo la función, se realiza el mismo proceso, se avalúa la condición

¿El número es igual a 1? Por supuesto que no. Pasamos al bloque else y hacemos exactamente lo mismo que la vez anterior, nos va a quedar lo siguiente.

return 3 * factorial(2);

Ahora es 2 el número que se pasa a la función, ya que la hemos vuelto a llamar, haremos el mismo proceso que hemos hecho.

¿El número es igual a 1? Por supuesto que no. Pero dense cuenta que cuando pasemos al bloque else el parámetro que se va a enviar va a ser (2 – 1) y eso es igual a 1. Como ven, este es el número que se va a enviar a la función.

¿1 es igual a 1? Por supuesto que sí. Entonces la función retorna el valor de 1.

El proceso que acabamos de describir es el siguiente:

return 4 * factorial(3);
return 3 * factorial(2);
return 2 * factorial(1);

Y ahora véanlo así, ¿cuánto es el factorial de 1? Pues 1, así que ya habremos resuelto uno de los casos, con eso, podemos resolver el resto.

return 2 * factorial(1) = 2 * 1 = 2

Ahora ya sabemos cuánto es el factorial de 2, con esto podemos saber cuánto es el factorial de 3.

return 3 * factorial(2) = 3 * 2 = 6

Y hemos dado la solución al factorial de 3, que era lo que necesitábamos para saber cuál era el factorial de 4.

return 4 * factorial(3) = 4 * 6 = 24

Y listo, habremos obtenido el resultado. Esto es una función recursiva y es así como funciona.



Nota: Una función recursiva debe tener una condición que le permita terminar, si esto no se hace, se estaría entrando en un bucle infinito.