La recursividad es una técnica potente de programación que puede utilizarse en lugar de la iteración para resolver
determinados tipos de problemas.
Por ejemplo, para escribir un método que
calcule el factorial de un número entero no negativo, podemos hacerlo a partir
de la definición de factorial:
Si n = 0 entonces
0! = 1
0! = 1
si n>0 entonces
n! = n * (n–1) * (n–2) * ... * 3 * 2 * 1
n! = n * (n–1) * (n–2) * ... * 3 * 2 * 1
Esto dará
lugar a una solución iterativa en Java mediante un bucle for:
// Método Java no recursivo para calcular el factorial de un número
public double factorial(int n){
double fact=1;
int i;
if (n==0){
fact=1;
}else{
for(i=1;i<=n;i++){
fact=fact*i;
}
}
return fact;
}
Pero
existe otra definición de factorial en función de sí misma:
0! = 1
n! = n
· (n – 1)! , si n > 0 (El factorial de n es n por el factorial de
n-1)
Esta definición da lugar a una solución
recursiva del factorial en Java:
// Método Java recursivo para calcular el factorial de un número
public double factorial(int n){
if (n==0){
return 1;
}else{
return n*(factorial(n-1));
}
}
Un método es recursivo
cuando entre sus instrucciones se encuentra una llamada a sí mismo.
La solución iterativa es fácil de entender.
Utiliza una variable para acumular los productos y obtener la solución. En la
solución recursiva se realizan llamadas al propio método con valores de n cada
vez más pequeños para resolver el problema.
Cada vez que se produce una nueva llamada al
método se crean en memoria de nuevo las variables y comienza la ejecución del nuevo
método.
Para entender el funcionamiento de la
recursividad, podemos pensar que cada llamada supone hacerlo a un método
diferente, copia del original, que se ejecuta y devuelve el resultado a quien
lo llamó.
En la figura siguiente podemos ver como sería
la ejecución del programa Java anterior para calcular el factorial de 3.
Un método
recursivo debe contener:
- Uno o más casos base: casos para los que existe una solución directa.
- Una o más llamadas recursivas: casos en los que se llama sí mismo
Caso base: Siempre ha de existir uno o más casos en los que los
valores de los parámetros de entrada permitan al método devolver un resultado
directo. Estos casos también se conocen como solución trivial del
problema.
En el ejemplo del factorial el
caso base es la condición:
if (n==0)
return 1;
si n=0 el resultado directo es
1 No se produce llamada recursiva
Llamada recursiva: Si los valores de los parámetros de entrada no cumplen
la condición del caso base se llama recursivamente al método. En las llamadas
recursivas el valor del parámetro en la llamada se ha de modificar de forma que
se aproxime cada vez más hasta alcanzar al valor del caso base.
En el ejemplo del factorial en
cada llamada recursiva se utiliza n-1
return n * ( factorial(n-1) );
por lo que en cada llamada el
valor de n se acerca más a 0 que es el caso base.
La
recursividad es especialmente apropiada cuando el problema a resolver (por
ejemplo calculo del factorial de un número) o la estructura de datos a procesar
(por ejemplo los árboles) tienen una clara definición recursiva.
No se debe utilizar la recursión cuando
la iteración ofrece una solución obvia. Cuando el problema se pueda definir
mejor de una forma recursiva que iterativa lo resolveremos utilizando
recursividad.
Para medir la eficacia de un algoritmo
recursivo se tienen en cuenta tres factores:
- Tiempo de ejecución
- Uso de memoria
- Legibilidad y facilidad de comprensión
Las soluciones recursivas suelen ser más lentas que las
iterativas por el tiempo empleado en la gestión de las sucesivas llamadas a los
métodos. Además consumen más memoria ya que se deben guardar los contextos de
ejecución de cada método que se llama.
A pesar de estos inconvenientes, en
ciertos problemas, la recursividad conduce a soluciones que son mucho más
fáciles de leer y comprender que su correspondiente solución iterativa. En
estos casos una mayor claridad del algoritmo puede compensar el coste en tiempo
y en ocupación de memoria.
De todas maneras, numerosos problemas
son difíciles de resolver con soluciones iterativas, y sólo la solución
recursiva conduce a la resolución del problema (por ejemplo, Torres de Hanoi o
recorrido de Árboles).
Ejemplos de Recursividad
Ejemplos de Recursividad
y en que tipos de programas se utiliza la recursion
ResponderEliminarSe utiliza en programas de resolución de patrones, como el algoritmo A estrella.
EliminarPara el manejo de arboles y grafos, así como las listas enlazadas, pilas y colas, tiene muchas aplicaciones
EliminarMUY BUENA EXPLICACIÓN, ADEMAS MUY GRÁFICO. EXCELENTE :D
ResponderEliminarMuchas gracias, me estaba rompiendo la cabeza, los graficos me hicieron entender mejor
ResponderEliminarExcelente, superexplicado, me gusta tu dedicación para explicar, quiero dejar un aporte al tema espero sirva http://usandojava.blogspot.com/2011/01/fibonacci-recursivo.html
ResponderEliminarExitos
Me alegro de que os haya ayudado a entender un poco más la recursividad.
ResponderEliminarMuchas gracias me he aclarado bastante
ResponderEliminarola k ase, muxa graxia
ResponderEliminarde nada
EliminarExcelente. La gráfica es muy ilustrativa y didáctica.
ResponderEliminar¿No sería mejor poner como condición de parada if ( n < 1 ) return 1;?
ResponderEliminarAsí aunque se metiese un número negativo no habría un desbordamiento de pila. O bien poner una excepción que diga que no se pueden meter números negativos.
100 puntos tu codigo
ResponderEliminarGracias a todos por tomaros un poco de tiempo y dejar un comentario. Es agradable saber que a al otro lado hay alguien a quien le está ayudando el blog sobre todo para entender el concepto de recursividad. ;)
Eliminarmuy buena explicación
ResponderEliminarYou're a fucking Yisus jajaja Gracias.
ResponderEliminarGracias por el aporte y por los graficos
ResponderEliminarGracias por los comentarios, me alegra saber que os ha sido útil. Saludos !!
ResponderEliminarGracias, bien explicado !
ResponderEliminarExcelente
ResponderEliminarGracias Ana!
EliminarMuy bueno, le agradezco que se tome su tiempo para ayudar a los demas !
ResponderEliminarDE verdad muy utila la explicacion, la primera pagina que veo que lo explica tan bien gracias a los graficos
ResponderEliminar¡Excelente explicación!
ResponderEliminarGracias!!
EliminarLo entenfi gracias a tu entrada,mil gracias!
ResponderEliminarGenial! Gracias a ti por seguir el blog.
Eliminarurn division(a-b, b) + 1;
ResponderEliminaren este caso para que sirve la coma??
Este comentario ha sido eliminado por el autor.
ResponderEliminarDe tantas páginas en la web , ésta tiene la Mejor Explicación Gráfica que he visto ! Felicitaciones por publicación .
ResponderEliminarMuchas gracias Marcos.
EliminarGracias, me has aclarado muchas dudas.
ResponderEliminar