El concepto de recursividad es uno de los más complejos y díficiles de entender en la programación orientada a objetos. Lo trataré de explicar con algunas ideas y algún ejemplo.
En la vida hay muchos conceptos que se utilizan a si mismos para explicarse. Una rama de un árbol a su vez tiene ramas, que a su vez puede tener ramas y así sucesivamente hasta que aparecen ramas que solo tienen hojas.
Al igual que en este ejemplo, muchos algoritmos se explican en términos de sí mismos. Los algoritmos que poseen esta particularidad se denominan recursivos.
Al igual que la mayoría de los lenguajes de programación, C# permite definir métodos recursivos. O sea, métodos que se llaman directa o indirectamente a si mismos. Y ahora la gran pregunta que se hacen todos….
Cuando y como termina entonces el método recursivo?
Ya se que puede parecer un proceso infinito, pero la clave está en que en cada llamada el problema se “simplifica” de tal modo que llegará el momento en que no hará falta llamar nuevamente al método recursivo. Recuerda que la rama tiene ramas, que a su vez tiene ramas… pero llega el momento en que se llega a una rama que solo tiene hojas.
Cabe resaltar que la recursividad es una herramienta muy importante en la programación que en muchos casos permite expresar algoritmos de forma simple y legible. Veremos ahora un caso muy simple en que la recursividad hace nuestro trabajo mucho más fácil.
Factorial de un número
Los mátemáticos suelen decir que n! = n * (n - 1)! Sin embargo, en programación, dicho de esta manera la solución sería infinita, ya que siempre podemos restar 1 hasta el infinito negativo. Por tanto debemos definir el factorial de un número para los números mayores o iguales que cero. Por tanto, la función factorial es muy fácil de expresar en C# mediante la recursividad. Este sería el código:
static long Factorial (long n)
1 {
2 if (n>=0)
3 {
4 // caso base
5 if (n == 0) return 1;
6 else return n * Factorial (n - 1);
7 }
8 else
9 throw new Exception(“Factorial de un negativo”);
10 }
Otra solución al cálculo de un factorial se puede expresar de manera muy simple utilizando un ciclo for.
static long Factorial (long n)
{
if(n<0)
throw new Exception(“Factorial de un número negativo”);
else if(n==0) return 1;
else
{
long result= 1;
//Seria multiplicar n * n-1 hasta que n = 0
for (int k = n; i >= 1; i –)
result = result * k;
return result;
}
}
Este ejemplo nos ilustra las principales reglas y pasos que debe seguir un método recursivo.
Ahora las 4 reglas de oro de la recursividad
1 - Caso base. Siempre tiene que haber al menos un caso base en que no se necesite la recursividad para resolver un problema.
2 - Toda llamada recursiva debe regresar hacia el caso base.
3 - Credibilidad. Asuma siempre que la llamada recursiva funcionará correctamente. Esto se fundamenta en la hipótesis de inducción, lo que quiere decir que no debemos preocuparnos por hacer el trozo de todos los largos caminos de llamadas recursivas, una labor que a veces ni uno mismo entiende.
4 - Nunca duplique el trabajo. No resuelva con una llamada recursiva por separado lo que ya ha sido resuelto en otra llamada.
Ahora ya tienes una idea de lo que significa que un método sea recursivo y como resolver algunos ejemplos sencillos con esta potente herramienta. Puedes practicar con algunos ejercicios sencillos como la sucesión de fibonacci, la suma de n números pares y otros ejemplos que se les ocurra. Trata de darle solución recursiva a problemas sencillos que hayas resuelto antes de modo iterativo.
Recuerda que en la programación, no se trata de leer muchos tutoriales y cursos, se trata de leer y escribir código.
En la segunda parte de este pequeño tutorial les comentaré sobre algunas técnicas y estrategias del ámbito recursivo como son “Divide y Vencerás” y “Backtracking” (Vuelta atrás) para resolver problemas un poco más complejos en los que la solución no se ve tan simple, así como algunos otros ejemplos y ejercicios resueltos.
Si tienen alguna duda o pregunta dejen un comentario.
