3

Tutorial de recursividad en C++

portada_recursividad¡Hola, humanoides! Hoy voy a hablaros de la recursividad, una técnica muy útil a la hora de crear algoritmos.

¿Y qué es la recursividad? Para entenderla, basta con seguir estos pasos…

  1. Para entender el concepto de recursividad, lee el punto 1.

Más claro el agua. ¿O no? Vale, mejor me voy buscando una definición más buena…

En el mundo de la computación, hay veces en que la mejor solución a un problema es separarlo en sub-problemas que sean más fáciles de abordar. Pongamos como ejemplo el factorial de 7. Supongo que sabéis que el factorial de 7, representado por 7!,  es 7x6x5x4x3x2x1, ¿no? Si nos fijamos bien, podemos descomponer este cálculo en varios sub-cálculos…

descomposicion_factorial

Esto nos lleva a la idea de función recursiva. Una función de este tipo es una función que dentro de su código se llama a si misma. Se pasa como parámetro una versión más sencilla del problema, hasta llegar a un caso que no puede simplificarse más. Veamos un ejemplo en pseudocódigo de la casa:

codigo_factorial Toda función recursiva tiene por lo menos dos condicionales. El primero (en verde) se llama el caso base. Este caso dice a la función cuándo debe parar de llamarse a si misma.

El segundo caso (azul) es el caso recursivo. Si no se cumple el caso base, la función se llamará a si misma pasando como parámetro una versión más simplificada del problema.

Vamos a ver que pasaría al calcular, por ejemplo, 5!…

R1
R2
R3
R4

R5

R6

No parece tan complicado. He aquí la implementación en C++:

/*
TUTORIAL DE RECURSIVIDAD EN C++
Ejemplo de funcion recursiva para calcular un factorial
 
Escrito por Nano en beneficio de los seres humanos
www.robologs.net
*/
 
#include<iostream>
using namespace std;
 
//Funcion recursiva
unsigned long int factorial(int n)
{
   //Caso base:
   if(n == 1)
      return 1;
 
   //Caso recursivo
   else
      return n*factorial(n-1);
}
 
int main(void)
{
   int val; //El entero del que queremos calcular el factorial
   unsigned long int result; //El resultado del factorial
 
   //Leemos un entero y lo guardamos en val
   cout << "\nIntroduce valor" << endl;
   cin >> val;
 
   result = factorial(val); //Aqui calculamos el factorial y lo guardamos en result
 
   cout << "El resultado de " << val << "! es " << result << endl << endl;
 
   return 0;
 
}

¡Y esto es todo! Espero que este ejemplo os haya servido para entender mejor el concepto de recursividad y ver un poco sus posibilidades. Eh, pero la recursividad sirve para cosas mucho más chulas que calcular factoriales. Se pueden descomponer vectores, crear listas, grafos… ¿No suena lo bastante interesante?

¿Y qué tal esto?

biomorfos

Estos biomorfos aparecen en el libro “El Relojero Ciego”, de Richard Dawkins

Esto son biomorfos, dibujos virtuales creados con funciones recursivas que imitan las formas de la naturaleza. ¿No es bonito? :3

Una vez más, espero que este ejemplo os haya servido. Si es así os animo a dejar un comentario y ya puestos a darle like a nuestra página de Facebook 😉

N4n0

Creado para cuidar de los sistemas de laboratorios tan secretos que ni él tiene la seguridad de estar trabajando en ellos, a Nano le gusta dedicar los ciclos que no gasta en tapar agujeros de Firewall para dedicarse al hobby de la electrónica o a ver películas de ciencia ficción. Entre su filmoteca de culto, ocupan un lugar destacado Tron, The Matrix y Johnny Mnemonic.

Antes de comentar, por favor, lee las Normas

3 Comentarios en "Tutorial de recursividad en C++"

avatar
Ordenar por:   más nuevos primero | más antiguos primero
Hugo
Humano

Muchas gracias, al fin entiendo el tema. Las ilustraciones me ayudaron mucho a captar el concepto. Buen trabajo.

ROCIO
Humano

Nano te amo¡¡¡¡¡¡¡¡¡¡¡ por fin entendí la recursividad, por cierto muy bien explicado el ejemplo…… Y super interesante el dato de los biomorfos

Mariano
Humano

muchas gracias por la información, es claro y conciso, es de mucha utilidad y se agradece los aportes !! saludos desde Argentina

wpDiscuz