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.

1- 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:

int Factorial (int n)
{
         if ((n == 0) || (n == 1))
                 return(1);
         else
                 return(n*Factorial(n-1));
}

Es importante decir tambin que todos los métodos recursivos se pueden hacer de forma iterativa, pero a veces el resultado se hace un poco confuso. Por ejemplo, el factorial de un numero n también se puede calcular de esta forma:

int Factorial (int n)
{
      fact = 1;
      for (int i=2;  i<=n;  i++)
            fact = fact * i;
      return fact;
} 

Ven como la forma recursiva es mucho más entendible y está basada en la propia definición de Factorial de n.

2- Calcular el máximo común divisor de dos numeros

Sean a y b dos números enteros no negativos. Entonces el máximo común divisor (mcd) entre a y b es el mayor entero c, que divide a y b.

Hay dos buenos algoritmos para resolver este problema, pero el más eficiente es el algoritmo de Euclides, que descubrío hace más de 2000 años, mucho antes que las computadoras, y lo curioso es que todavía nadie ha encontrado un mejor algoritmo para calcular el mcd de dos números.

El algoritmo de Ecuclides dice:
Si a y b son enteros, con a>b (porque si b>a entonces los intercambianos), entonces el mcd (a,b), es igual al mcd entre a y el resto de la división entre a y b. Traten de demostrarlo!

Bueno, vamos ya al código:

int MCD (int a, int b)
{
      if(b==0)
            //Caso base, cuando el resto sea 0
             return a;
      else
             //Llamamos pasandole el resto de la división
             return MCD (b, a%b);
}

Bueno, hasta aquí esta primera parte del tutorial sobre recursividad en C#. Después seguiremos hablando sobre este tema, y veremos algunas cosas un poco más interesante, hablaremos de algunos algoritmos. Como salir de un Laberinto? Se pueden ubicar 8 damas en un tablero sin que se amenacen? Como hacer una busqueda eficiente?
Interensante verdad? Nos vemos en la proxima entrega.

Recursividad con C# 2da parte
Recursividad con C# 3ra parte