Recursividad con C# (1)

El concepto de recursividad es uno de los más complejos y difíciles 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 matemá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 también 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 número 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 números

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 descubrió 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 Euclides dice:

Si a y b son enteros, con a>b (porque si b>a entonces los intercambiamos),

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);

}

Recursividad con C# (2)

Como lo prometido es deuda, empezaremos esta segunda parte del

minicurso de Recursividad en C# con el clásico Hanoi, y luego hablaremos

sobre algunas técnicas asociadas al uso de la recursividad, como son

“Backtracking” y “Divide y Vencerás”. Además, resolveremos paso a paso

varios de los clásicos problemas de recursividad.

Según mi profesor de programación (Dr. Miguel Katrib), el juego de las

torres de Hanoi es el poder expresivo de la Recursividad, y creo no hay

mejor ejemplo que este para empezar a comprender como verdaderamente

funciona la recursividad en C#.

El juego consiste en ir moviendo discos de la torre original de la izquierda de

modo tal que finalmente queden en la misma posición en la torre de la

derecha. Los movimientos de los discos deben hacerse bajo las siguientes

restricciones: solo podrá moverse un disco a la vez y nunca podrá ubicarse

un disco de mayor diametro sobre uno de menor diametro. La torre del

centro puede utilizarse de modo auxiliar para el traspaso de los discos.

En la imagen de la derecha se muestran los movimientos a realizar para

mover 3 discos. ¡Imaginen ahora la cantidad de movimientos a realizar para

mover 10 discos! Lo que se quiere es un algoritmo que nos diga los

movimientos a efectuar para mover una cantidad “n” de discos.

Analicemos ahora el problema:

1- Si la cantidad de discos a mover es 1, entonces movemos el disco de la

torre de origen a la torre de destino.

2- Supongamos que sabemos mover n-1 discos desde la torre de origen

hasta la torre auxiliar del centro.

3- El tercer paso consiste en mover el disco mayor que ha quedado solo en

la torre izquierda hacia la torre de destino.

4- Mover esos n -1 discos desde la torre auxiliar (que hace de origen) hacia

la torre de la derecha.

¿Cómo sabemos mover n-1 discos?

Como se podrá notar, este algoritmo se utiliza a si mismo y está basado en

el principio de inducción matemática. Además, si no cree que podamos

mover n-1 discos, entonces veamos si podemos mover n-2 discos, si

tampoco lo cree podemos seguir hasta que tengamos que suponer que

sabemos mover 1 disco, lo cual es cierto.

El método Mover a continuación escribirá como salida los movimientos a

realizar para mover una cierta cantidad de discos que se le indica como

primer parámetro. Los restantes parámetros serían los nombres de las

torres de origen, auxiliar y destino.

De modo que cuando haríamos algo como:

La salida sería:

Seguro notaste que cada vez que se hace una llamada recursiva, la

cantidad de discos que se pasa como primer parámetro disminuye en 1. De

modo que en algún momento la cantidad de discos será 1, y entonces ya no

se hará más ninguna llamada recursiva y el método Mover sabrá retornar a

quién lo llamó.

Es C# quien lleva todo este proceso de saber como regresar y quien

garantiza que los parámetros tengan los mismos valores que tenían antes

de haberse hecho la llamada. Si todavía desconfía del trabajo recursivo,

intente manualmente seguir el rastro de una llamada original a mover 4

discos.

Estrategia de “Divide y Vencerás”

Una estrategia importante en la recursividad es la llamada “Divide y

Vencerás”. La implementación de soluciones basadas en esta estrategia no

sería posible sin la recursividad. Dar un concepto de esta técnica o

estrategia no es tan complicado. Primero veamos un ejemplo.

Búsqueda Binaria

Considere que los elementos de un array de números enteros están

ordenados de menor a mayor, por ejemplo {2, 3, 5, 7, 9, 12, 15, 18, 20}. Se

quiere saber si el elemento 17 está en el array.

Lo que haremos será buscar el elemento que está en la mitad del array (9

en este caso). Si el elemento que buscamos es igual a este, hemos

terminado. De lo contrario, como los elementos del array están ordenados,

si el elemento buscado es mayor que el del medio, buscamos a la derecha,

si es menor, a la izquierda. En este caso 17 es mayor que 9, y por tanto hay

que buscar en {12, 15, 18, 20}. Ahora hacemos lo mismo, en este caso, hay

que tomar una decisión, ya que como la cantidad de elementos es par, hay

que ver si tomamos como el elemento del centro, el de más a la izquierda o

el de más a la derecha (el 15 o el 18). Por ahora lo haremos con el que esté

en el centro más a la izquierda (el 15). Como 17 es mayor que 15

buscaremos entonces en {18, 20}. El del medio es el 18. Y como el 18 es

mayor que 17, entonces buscaremos en {18}. El elemento medio es el

propio 18 que no es igual a 17. Como ya no se puede seguir haciendo

subdivisiones, entonces podemos concluir que 17 no está en el array.

Por lo que el código sería el siguiente:

Note como, además de cumplir las 4 reglas de la recursividad, el método

recursivo contiene dos llamadas recursivas que se aplican a dos posibles

“divisiones” del problema original. Generalmente se considera que los

algoritmos que contienen más de dos llamadas recursivas son algoritmos de

“Divide y Vencerás”.

Podemos resumir entonces que esta estrategia consta de dos partes.

1- La división. Es donde el problema se divide en problemas más pequeños

que a su vez re resuelven recursivamente.

2- La solución del problema original se forma a partir de estos problemas

más pequeños.