Recursividad

CONCEPTOS BÁSICOS

•Un objeto es recursivo cuando se define en función de sí mismo, es decir, interviene en su propia definición.
•La recursividad es la propiedad mediante la cual unsubprograma o rutina puede llamarse a sí mismo.
•Utilizando la recursividad, la resolución de un problema se reduce a uno esencialmente igual pero algo menos complejo.
•Características que debencumplir los problemas recursivos:
–La recursividad debe terminar alguna vez: caso base
–Cada nueva formulación estamos más cerca del caso final (o base

EJEMPLO DE PROBLEMA RECURSIVO•FACTORIAL DE UN NÚMERO ENTERO POSITIVO
Sin recursividad:
n! = n (n-1) (n-2)........1
(n-1)! = (n-1) (n-2).......1
Ley de recurrencia:
n! = n (n-1)! si n>0
0! = 1 si n=0

IMPLEMENTACIÓNEN PASCAL MEDIANTE FUNCIONESFunción no recursiva o iterativa
functionfactorial(n: word): real;
vari: word; aux: real;
begin
aux:= 1;
fori := 1 to n do aux:= i * aux;
factorial:= auxend;
Función recursiva
functionfactorial(n: word): real;
begin
ifn > 0
thenfactorial:= n * factorial (n-1)
elsefactorial:= 1
end;

PROCESO DE EJECUCIÓN. PILA RECURSIVA

•Ejecucióndel programa:
–Bajo una llamada recursiva el sistema reserva espacio (tabla de activación) donde almacenar una copia de los objetos locales y parámetros del subprograma en ese momento.
–Latabla de activación se amontona sobre las llamadas recursivas anteriores formando lo que se conoce como pila recursiva.
–Este proceso termina cuando un nuevo valor del parámetro no produceuna nueva llamada recursiva (se alcanza el caso base).
–Una vez alcanzada esta situación el sistema va liberando el espacio reservado conforme los subprogramas se van ejecutando sobre su tablade activación.
–Este proceso finaliza con la llamada inicial.

REPRESENTACIÓN GRÁFICA DEL PROCESO DE EJECUCIÓN DE UN PROGRAMA RECURSIVOBEGIN------------------------------LLAMADA AL...