La recursividad es un mecanismo que parece no aportar nada y que le resulta muy es algo complicado de entender. Se puede resumir como un mecanismo muy potente con el que se consigue que determinados programas mejoren su rendimiento y se escriban de forma más simple y clara, facilitando la actualización y modificación del código.
En programación, se usa el término recursividad para referirnos a procedimientos o métodos que contienen en su implementación llamadas a sí mismo, es decir un método es recursivo si para ejecutarse se llama así mismo.
Aspecto de la declaración de un metodo recursivo:
Sentencia;
}
metodoRecursivo(
En negrita es la llamada que el método se hace a sí mismo.
Pero, si para ejecutar a un método hay que haer uina llamada al mismo método que a su vez hará una llamada al mismo método, y así sucesivamente, ¿no habremos entrado en un bucle infinito que hará que nunca terminemos?.
No, si las cosas se hacen bien, aunque evidentemente, es posible hacerlas mal.
¿Qué debemos tener en cuenta a la hora de saber si un método recursivo está bien definido?
* Además de la llamada al propio método, deben existir otras sentencias en la definición del método que establezcan al menos un caso base, es decir, un caso para el que se conoce la solución, y para el que la llamada al método puede devolver un valor o terminar la ejecución sin necesidad de volver a invocar de nuevo al propio método.
* Cada nueva llamada al propio método debe reducir el problema, es decir, debe acercarnos más al caso base.
* La solución debe ser correcta para los caso no base. Es decir, debemos ser capaces de expresar correctamente la solución de un caso a partir de las soluciones de casos menos complejas, para poder construir la solución de cualquier caso a partir de las soluciones del caso base.
ejemplo del calculo factorial de un número:
El factorial de un número entero positivo "n" se representa como n!(que se lee como "n factorial").
Sabemos que dado un número entero positivo, el factorial se puede definir de dos formas:
Definición Iterativa:
Como el producto de todos los números enteros compredidos entre 1 y el propio número:
n!=n*(n-1)*(n-2)*...*3*2*1. Además, por convenio, para extender la definición también al cero, se define 0!=1
Para calcular el factorial de esta forma, tenemos que repetir un ciclo en el que se vaya acumulando el producto del númeropor el anterior, hasta que lleguemos a uno.
Definición Recursiva
Como el producto del propio número por el factorial del número anterior.
Es evidente que (n-1)! = (n-1)* (n-2)* ... *3*2*1, lo que nos lleva a poder escribir que n!=n*(n-1)!, siendo además 0!=1 igual que antes. Acabamos de hacer una definición por recurrencia del factorial de un número. "el factorial de un número vale 1 si el número es 0, y el producto del propio número por el factorial del anteior, en otro caso."
Para calcular el factorial de esta forma, es como su le encargáramos la tarea a una persona que no sabe calcular el valor final del factorial n, pero sabe que n * (n-1)*(n-2)!, y le pregunta a su vez a a otra persona el valor de (n-2)!, y así sucesivamente hasta que llegamos a preguntarle a una persona el valor de 0! y esa persoba responde que 0! = 1. A partir de ese momento, la persona que le preguntó tiene toda la información para calcular 1!, lo calcula, y le responde a la persona que le preguntó, que completa el cálculo de 2!, y así sucesivamente, hasta llegar a la persona que calcular(n-1)!, que completa el cálculo y le proporciona su valor a quien le preguntó, que multiplica ese valor por n y obtiene el valor de n!.
La recursividad ees una poderosa herramienta en programación y ofrece una alternativa a las soluciones iterativas complejas de algunos algoritmos.
Razones por las que se debe usar la recursividad:
1.- Los problemas resultan más fáciles de resolver que con estructuras iterativas.
2.- Proporciona soluciones más simples.
3.- Proporciona soluciones elegantes.
En el caso del factorial se a podido ver que habia dos posibles soluciones, una iterativa y ora recursiva.
No solo no existen casdos en los que sea obligatorio, sino que siempre existe una solución iterativa, y ésta siempre será más eficiente, es decir, necesitará cosumir menos recursos de memoria y de CPU, y obtendrá la solución en menos tiempo.
Lo que ocurre es que a veces, por la naturaleza recursiva del problema, no es fácil encontrar la solución iterativa, o resulta complicada y difícil de entender.
La recursividad se debe usar cuando sea realmente necesaria, es decir, cuando no exista una solucion iterativa simple. Cuando las dos soluciones son fácilmente explicables, siempre será preferible la solución iterativa.
Por otro lado, la recursividad requiere hacer una asignación dinámica de memoria, que no es posible en todos los lenguajes de programación. Ejemplos, en Java si lo es.
Cada vez que se hace una llamada al método recursivo, es necesario guardar en la pila(stack) todos los datos de la llamada que aún no ha terminado(son las variables de memoria que tenga definidas el método), lo que se conoce como entorno volátil de esa ejecución.
Essto incluye almacenar en la memoria todos los valores de registro del microprocesador, para poder restablecerlos posteriormente y continuar por el mismo punto de la ejecución de esa llamada que se habia dejado.
Cuando hay muchas llamadas sucesivas, estas llamadas se van almacenando en la pila(stack), de forma que se irán retirando de ella en orden contrario al que entraron o se introdujeron.
Ejemplo, el último en entrar es el primero en salir. (estructura LIFO: Last-IN, First-OUT)
Todo ese tiempo de CPU dedicado a:
- Guardar los datos de cada ejecución en la pila,
- cargar los de la nueva llamada para cuando al final ésta termine
- ir de nuevo sacando esos valores de la pila en orden contrario a como se introdujeron
- para restaurarlos en la CPU y completar la llamada,
Con una solución iterativa sólo tendremos un método ejecutándose, por lo que sólo necesitaremos memoria para una copia de cada una de las variables que usa ese método. Por otro lado, no hay que hacer ninguna operación de almacenar en la pila los datos de ejecución para posteriormente reanudarla, ya que la llamada al método iterativo se ejecuta hasta finalizar, sin intervención de ninguna otra llamada.
Función Fibonacci
LA función Fibonacci calcula el valor del término n-ésimo de la sucesión de Fibonacci, en la que el primer término es 0, el segundo1 y a partir de ahí, cada nuevo término se calcula como la suma de los dos inmediatamente anteriores. Puede también inicializarse los dos primeros términos con otros valores, pero lo que no cambia es la forma de obtener los sucesivos términos.
Por tanto, la función Fibonacci se puede definir como:
- Fibonacci(n)=n, si n=0 ó n=1
- Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2), si n > 1
static int fibonacci (int n) {
if ((n == 0) || (n == 1)) {
return 1;
} else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
El algoritmo recursivo que implementa a esta función es muy sencillo de hacer, pero muy ineficiente. Si intentas calcular el término 40 de la sucesión, verás cómo tarda un tiempo considerable en resolverlo, y si introduces un valor más alto, posiblemente parezca que el ordenador se ha bloqueado debido a lo que tardar en responder. Este tiempo depende del ordenador en el que se ejecuta.
No hay comentarios:
Publicar un comentario