PDF de programación - Eliminación de la recursividad mediante Pilas

1

Eliminación de la recursividad mediante Pilas

Cada vez que se genera una llamada a una rutina recursiva se crea un registro de activación donde
se almacenan las constantes, variables y parámetros por valor sobre las que se ejecutará esa copia del
programa. Además, las llamadas recursivas se comportan como una pila: la última copia generada es
la primera que se termina de ejecutar y además se ejecuta sobre los últimos valores generados para
los parámetros. De forma que se comportan como si hubiésemos almacenado variables y parámetros
en una pila, y luego fuésemos recuperando estos datos y ejecutando el procedimiento en cuestión
sobre cada una de ellas (en realidad, esto es lo que ocurre). Así, para eliminar la recursividad y
obtener una versión iterativa de un programa se puede seguir el proceso siguiente:

1. Mientras que los parámetros no se correspondan con el caso base, de forma iterativa:

a) Obtener los parámetros y variables locales sobre los que se ejecutaría cada copia recursiva

y,

b) Almacenarlos en pilas separadas.

2. Mientras las pilas no estén vacías:

a) Sacar los parámetros y variables locales introducidos y,
b) Ejecutar sobre ellos el código que está después de la llamada recursiva.

Ejemplo. Proceso recursivo que imprime en orden inverso una lista implementada de forma dinámi-
ca.
procedure Imprimir lista inversa (L: tLista);
{Objetivo: imprimir el contenido de una lista a la inversa
Entrada:
Salida :
begin
1.
2.

L: inicio de la lista
por pantalla }

if L<>nulo
then begin
3.
4. write(Lˆ.info);

Imprimir lista inversa (Lˆ.sig);

5. end;

end;

Registros de activación y ejecución para una lista de tres nodos:

Imprime_lista(copia 1) L-> 1er. nodo dirección retorno: 3 paso 1 L -> 2º nodo dirección retorno: 3 L -> 3er nodo paso 2 Imprime_lista(copia 2) Imprime_lista(copia 3) dirección retorno: 3 L -> nulo paso 3 Imprime_lista(copia 4) En este ejemplo, tenemos un único parámetro —un puntero a un nodo de la lista— y ninguna

variable local. Creamos la versión iterativa mediante el uso de pilas.
procedure Imprimir lista inversa (L: tLista);

2

uses

var

TDA Pila; {con tInfo=tLista}

Pila: tPila ; begin
PilaVacia(Pila);

{Vamos almacenado los valores de los parámetros en la pila}
while L<>nulo do
begin

Meter(Pila, L);
L:= Lˆ.sig;

end;
{Ya están todos los parámetros introducidos en la pila}
{ejecutamos las instrucciones después de l
while not EsPilaVacia(Pila) do
begin

llamada recursiva}

Cima (Pila,L);
quitar(Pila);
write(Lˆ.info);

end;

end;