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  |