Entendiendo la recursividad

Jul 24, 2008 Tutoriales C# 23 comentarios

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.

Compartir:

23 comentarios

Forma parte de nuestra discusión y síguela de cerca

Hola que tal. Tendras algunos ejemplos para empezar? esto es dificil para mi, y necesito algunos ejemplos como para fijarme en la resolución y practicar. Gracias!

Autor: Nano | Fecha: Sep 16, 2009.

mostrar el menor digito de un munero
ejemplo 321 = 1
en visual estudio c charp

Autor: diego | Fecha: Ene 28, 2010.

lo puedes hacer recursivo o no. El metodo recursivo quedaría algo así, no lo he probado ni nada.

//Le pasamos el numero, una posicion y la variable min.
int MenorDigito (string num, int index, int min)
{
//condicion de parada
if ( index >= num.Length )
return min;

//actualizo el minimo si es necesario
if ( min> int.Parse(num[index]) )
min= int.Parse(num[index]

//Aqui va la llamada recursiva
return MenorDigito(num, index+1, min)

}

Noten que uso el metodo int.Parse() para convertir de string a entero.

Autor: Tomy | Fecha: Ene 31, 2010.

He visto varios algoritmos para el factorial, pero el tuyo es tan sencillo que en dos pasadas ya me lo aprendí de memoria. Hoy tengo un exámen de trabajo y con esto que pusiste aquí me vas a ayudar a pasarlo. Gracias, majo, eres tremebundo.

Autor: JPMarichal | Fecha: Oct 21, 2010.

quisiera que me muestren un programa en Csharp que trate de:
al darme cuatro puntos en el plano determinen si estos forman un cuadrado y asi hallar el lado la diagonal y poder calcular el area de dicho triangulo

Autor: hermione | Fecha: Dic 16, 2010.

hola ke tal, ke padre esta agina eh, me ha servido en mucho de verdad gracias

Autor: katy | Fecha: Feb 23, 2011.

kisiera aprender mas en c sharp, me podran ayudar???

Autor: katy | Fecha: Feb 23, 2011.

Quisiera que me dieras una ayudita con un programa recursivo, el programa trata de lo siguiente:
Ordenar en forma ascendente una matriz de n números, espero que alguien me ayude :D

Autor: Yolmax | Fecha: May 4, 2011.

Hay dos algoritmos de ordenación recursivos por excelencia y bien conocidos, de hecho, hace un tiempo escribí sobre ellos, aquí te dejo los enlaces:

Merge Sort
Quick Sort

Autor: Tomy | Fecha: May 6, 2011.

(y)(y)(y)(y)(y)(gracias!!!!!!!!!!!!

Autor: ydrat | Fecha: Jul 31, 2011.

Necesito que me indiquen como se hace: 1) dado un vector de 10 posiciones, imprimirlo en pantallas utilizando un metodo recursivo. Imprimir l numero de la posicion y el valor que tiene cargado.

Muchas gracias
Alejandra

Autor: Alejandra | Fecha: Oct 12, 2011.

Quisera que me ayuden como puedo hacerlo en recursivo Un granjero ha comprado una pareja de conejos para criarlos y luego venderlos. Si la pareja de conejos produce una nueva pareja cada mes y la nueva pareja tarda un mes más en ser también productiva, ¿cuántos pares de conejos podrá poner a la venta el granjero al cabo de un año?

Autor: liz | Fecha: Oct 30, 2011.

@Alejandra: Ese algoritmo es bastante sencillo, pero no veo porque tengas que usar la recursividad… utiliza mejor un ciclo for, puedes ver algunos ejercicios de array muy parecidos.
@liz: Ese es el clásico problema de Fibonacci! de ahí es que nacen los números de Fibonacci, que tienen una gran aplicación en muchas areas de la computación y la matemática. La respuesta es Fib(12), que es 144. Puedes ver bien el problema resuelto en este enlace y el algoritmo recursivo es bastante sencillo:

public long Fibonacci(int n)
{
           if(n==1 || n==2)
                return 1;
          else
                return Fibonacci(n-1) + Fibonacci(n-2);
}

No lo he probado, pero creo que funcionará

Autor: Tomy | Fecha: Oct 31, 2011.

me gustaria que me ayudes es un programita recursivo
Calcular la potencia de un real elevado a un entero positivo, teniendo en cuenta que:

x^0=1
x^n=(x*x)^n/2, si n>0 y es par
x^n=x*(x^n-1), si n>o y es impar

gracias

Autor: liz | Fecha: Nov 18, 2011.

Un ejemplo de recursividad y iteracion con Matrices en C# estaria demadiaso bien, espero lo publiques que me compleja mucho ese tema…

Autor: Fidel | Fecha: Nov 21, 2011.

me gustaria saber mas sobre recursividad de arreglos

Autor: Inda | Fecha: Feb 10, 2012.

Es bueno encontrar paginas con contenido de vez en cuando. Agradezco lo didactico de la explicacion.

Saludos

Autor: Matias | Fecha: Mar 19, 2012.

Hola, me pareció interesante el blog y quisiera que me ayudaran con un programita que estoy haciendo, un Analizador Sintáctico me da un AST del código fuente del lenguaje Java, quisiera contar los nodos del árbol que se crea, no todos por supuesto si no los q cumplen una condición X.

Autor: Robert | Fecha: Mar 31, 2012.

@Robert, si estás haciendo un compilador (lo digo por lo del arbol de sintaxis abstracta), te deseo suerte, porque la vas a necesitar ;) En ese caso deberás implementar un recorrido DFS o BFS (algoritmos para recorrer grafos y árboles) añadiéndole la condición.

Autor: Tomy | Fecha: Abr 1, 2012.

Buenos dias, necesito por favor me ayuden con este algoritmo. necesito desarrollarlo en pseudoformal y en lenguaje c++
Dado un numero N entero positivo de 8 dígitos, desarrolle un programa que genere un nuevo numero N con el intercambio del dígito correspondiente a la i-esima posición con el digito de la j-esima posición.

Ejemplo: N inicial=54789843 i-esimo=7 j-esimo=4 Nfinal = 59784843

Muchas gracias de antemanos.

Autor: CESAR ORAMAS | Fecha: Abr 11, 2012.

me ayuda.mucha ste sitio graxias…..

Autor: quilian | Fecha: Ene 10, 2013.

[...] te reto a que trates de hacerlo solo, tal vez usando más o menos un código similar al de Fibonacci, que escribí hace un buen [...]

Autor: Calcular los n primeros elementos del Conjunto de Wirth | puntopeek | Fecha: Abr 4, 2013.

Amigoooo xfabor me puedes ayudar si nos puedes mostrar este ejercicio en recursividad quiero aprenderlo lo q pasa es q tengo examen y el pseudocodigo mas si puedes gracias

Autor: kevin | Fecha: Dic 18, 2013.

Escribe tu comentario

Requerido.

Requerido. No público.

Si tienes alguno.