Introducción Diccionario castellano
recurrir volver una cosa al sitio de donde salió; retornar, repetirse, reaparecer; (poco frecuente) recurrir a algo -> hacer uso de ello (más común)
Introducción Subprogramas recurrentes
se invocan (llaman) a sí mismos definidos en términos de sí mismos
Circularidad Recurrencia inútil int P(){ return P; }//fin P
Circularidad Termina con un error de ejecución: no hay más memoria (p.ej:'stack overflow') ¿ Por qué ? cada vez que un programa P llama otro Q debe guardarse una indicación del punto en P donde el control debe retornar al finalizar la ejecución de Q las llamadas a procedimientos pueden encadenarse arbitrariamente Q1 -> Q2 -> Q3 -> … -> Qn -> …
Circularidad Hay una estructura de datos donde se almacenan sucesivos puntos de retorno: En general se tiene: P -> Q1 -> Q2 -> Q3 -> … -> Qn donde Qn es el subprograma que se está ejecutando
Circularidad Paralelamente, se ha formado la estructura de "puntos de retorno": p0, p1, p2, …, pn-1 p0 -> punto de retorno en P p1 -> punto de retorno en Q1 … pn-1 -> punto de retorno en Qn-1
Circularidad La estructura crece con cada nueva llamada (un lugar) y decrece al terminar la ejecución de un subprograma.
La estructura se comporta como una PILA (análogo a una pila de platos)
Circularidad El tope de la pila es el punto donde debe retornarse el control tras la terminación del subprograma corriente.
Por lo tanto, si el subprograma corriente llama a otro, el correspondiente punto de retorno debe colocarse como nuevo tope de la pila
Y al finalizar un subprograma, se usa el tope como dirección de retorno y se lo remueve de la pila.
pn-1 pn-2 . . .p1 p0
Circularidad Volviendo al ejemplo de "recurrencia inútil":
la pila crece infinitamente, pero la memoria de la máquina es finita, por lo tanto, en algún momento no hay más memoria (stack overflow = desbordamiento de la pila)
Ejemplo void ejemplo P(){ int x; scanf("%d",&x); if esPrimo(x) printf("Es Primon"); else printf("No es Primon"); P();//llamada recursiva }
Ejemplo (continuación) En principio, permitiría implementar un programa interativo.
Pero también termina por desbordar la pila (stack), en las implementaciones elementales.
Este es un ejemplo de recurrencia infinita
Circularidad
Estas recurrencias: pueden tener sentido en principio
pero terminan por desbordar la memoria (al menos con las implementaciones comunes de llamadas a subprogramas)
| Página siguiente |