Recursividad en la memoria

Solo disponible en BuenasTareas
  • Páginas : 10 (2442 palabras )
  • Descarga(s) : 0
  • Publicado : 31 de marzo de 2011
Leer documento completo
Vista previa del texto
Recursividad en la memoria
Introducción
La recursividad es una técnica en la que un procedimiento o función se hace llamadas así mismo hasta finalizar su proceso.
Las definiciones recursivas en las mayoría de las computadoras se implementan finalmente utilizando una pila en tiempo de ejecución, aun cuando el sistema operativo realiza todo el trabajo de implementación de la recursión y elcódigo fuente no incluye ninguna indicación de cómo se realiza esto. E.W. Dijkstra introdujo la idea de utilizar una pila para implementar la recursión. Para comprender mejor la recursión y ver cómo funciona, es necesario analizar el procesamiento de las llamadas a métodos y estudiar las operaciones realizadas por el sistema en la invocación de un método y en la salida de un método.
Dichas llamadas amétodos influyen en la recursividad, ya que un método recursivo se manda a llamar así mismo, o bien el método invocador tiene el mismo nombre del método invocado, por lo cual se da la recursividad.
También se hablará sobre los registros de activación, los cuales almacenan la información necesaria para que nuestros métodos pueden ejecutarse de la forma más apropiada, una de las cosas almacenas enlos registros de activación son las variables locales de dichos métodos, así como la dirección del invocador. Pero dichos registros de activación son desechados al finalizar el método, por lo tanto su vida es corta pero muy útil. Y se dirá cuál es el único método que si conserva su registro de activación.
Existen diferentes tipos de recursividad, de las cuales algunas serán explicadas brevementemás adelante.
El objetivo de dicho ensayo es conocer el uso de la recursividad y entender cómo es que la recursividad funciona en la memoria o pila de la computadora. Saber como varia la pila en tiempo de ejecución mientras se van invocando los métodos en forma recursiva, ya sea directa o indirectamente.

Recursividad en la memoria
Las definiciones recursivas se utilizan con frecuencia paradefinir funciones y secuencias de números. Un ejemplo muy claro de esto seria, la función factorial de algún número, la cual se puede definir de la siguiente manera:
n!= 1 , si n=0 (paso básico)
n!= n*(n-1)! , si n>0 (paso inductivo)
Usando esta definición, podemos generar la siguiente secuencia de números:
1 , 1 , 2 , 6 , 24 , 120.
Los cuales son factoriales de los números: 0 , 1 , 2 , 3 ,4 , 5.
Las definiciones recursivas de secuencias poseen una característica poco conveniente: esta es que para que podamos determinar el valor de un numero Sn de una secuencia, primero tenemos que calcular los valores de los elementos anteriores, S1… Sn. Continuando con el ejemplo del factorial de un numero se puede comprobar lo antes mencionado, por ejemplo si quisiéramos calcular el valor de3!, lo primero que se tiene q hacer es calcular los valores de los anteriores números; 0! , 1! , 2! , y en términos computacionales, este proceso no es muy aconsejable ya que se hacen cálculos haciendo un rodeo.
Las definiciones recursivas son empleadas en Java casi sin ningún esfuerzo, por ejemplo el método de la factorial que se presenta a continuación:
int factorial (int i)
{
If (n==0)return 1;
else return n*factorial (n-1);
}
Este método se manda a llamar de forma recursiva hasta que n sea igual a 0, es decir; cuando ya se haya obtenido el factorial de un numero n, mientras no se cumpla la condición el método se seguirá invocando así mismo.
La recursividad se implementa utilizando una pila en tiempo de ejecución, la idea de la pila la introdujo E.W. Dijkstra, paraentender mejor la recursividad tenemos que saber comprender el procesamiento de las llamadas a los métodos.
Llamadas a métodos: cuando un método es llamado sus valores se inicializan con sus parámetros actuales, además de que el sistema tiene que saber dónde reanudar el programa una vez que el método se ha finalizado. Un método tanto puede ser llamado por otros metros o también por el programa...
tracking img