PDF de programación - Tema 5.- Recursividad

Programación. Tema 5: Recursividad


(16/Mayo/2004)



Apuntes elaborados por: Raquel López, Eduardo Quevedo y Aaron Asencio
Revisado por: Javier Miranda el ????


Tema 5.- Recursividad

NOTA
Todos los ejemplos que se exponen en este tema se pueden
realizar utilizando la implementación del algoritmo “Pila” del tema anterior.
Donde se encuentra la llamada a recursividad utilizamos el “Push” y en el
return de la recursividad utilizaremos el “Pop”.


La recursividad es posible gracias a la existencia de pilas. Las
soluciones recursivas suelen ser bastante cortas pero cubren mucho más
espacio en la memoria del ordenador, este es el principal inconveniente de las
soluciones recursivas. Esto se debe a que si un programa recursivo tiene
variables dentro del mismo programa éstas se crearán nuevas cada vez que
se ejecute. Por este motivo en los procedimientos y funciones recursivos
evitaremos pasar como parámetros arrays, matrices, …, ya que estaremos
haciendo un uso innecesario de la memoria. Si lo que queremos es una
variable global entonces deberá estar en el programa principal. Por último
aclarar la utilización de los parámetros de entrada (in) y de salida (out):

IN Se comportan como constantes, no se pueden cambiar.

Los valores introducidos en la pila no se modifican.

OUT Son parámetros variables. Los valores se copian en la



Los programas recursivos tendrán casi siempre la siguiente estructura:

pila al elemento anterior.

Avance
Condición de parada
Procesamiento


Se vera más claro con un ejemplo:

if N = 0 then

return;
end if;
Int_IO.Put (N);
Escribir (N – 1);
Int_IO.Put (N);



procedure Escribir ( N : in Natural) is
begin



end Escribir;



1

Programación. Tema 5: Recursividad


(16/Mayo/2004)

¿Qué es lo que sucedería?

En la pantalla veríamos

1 2 3 3 2 1


La Pila la crea el propio compilador en
ella guarda todas las variables, parámetros
y procedimientos, así como la dirección de
retorno (línea donde se realizó la llamada
anterior). Esta Pila se irá vaciando poco a
poco se va deshaciendo el trabajo.



Algunos ejemplos de recursividad:


Escribir “3”

Escribir “2”

Escribir “1”

Para escribir una palabra al revés utilizando recursividad tendremos en
cuenta que si escribo a la ida escribiré la frase de forma correcta
mientras que si escribo a la vuelta se escribirá la frase al revés.



return;

if N > Frase’Length then

end if;
Escribir (N + 1);
Put (Frase (N));

Frase : String (1 .. 4) := “Hola”;
procedure Escribir (N : in Natural) is
begin



end Escribir;



¿Qué es lo que sucedería?



En la pantalla veríamos



Escribir “L”


Escribir “A”



ALOH

Escribir “O”

Escribir “H”



2

Programación. Tema 5: Recursividad


(16/Mayo/2004)

Para calcular el factorial de cualquier número, es muy útil utilizar la

recursividad, veamos como se haría:


function Factorial (N : in Natural) return Natural is
begin
if N=0 then



else



end if;
end Factorial;

return N*Factorial (N-1);

return 1;



¿Qué es lo que sucedería?



Factorial (0)

Factorial (1)

Factorial (2)

Factorial (3)

Factorial (4)

Factorial (5)

1

1*1=1

2*1=2

3*2=6

4*6=24



Casi todos las funciones y procedimientos iterativos pueden realizarse
con funciones o procedimientos recursivos; como por ejemplo la
búsqueda binaria.

Resultado
5*24=120



procedure Búsqueda_Binaria (Tabla : in T_Tabla;
Valor : in Integer;


Posicion : in out Integer )
is



begin



Primero : Natural := Tabla’First;
Ultimo : Natural := Tabla’Last;
Mitad : Natural := (Primero + Ultimo)/ 2;

if Tabla’Lenght then


raise No_Encontrado;



3

Programación. Tema 5: Recursividad


(16/Mayo/2004)

Búsqueda_Binaria (Tabla (Primer .. Medio - 1),


Valor,



Búsqueda_Binaria (Tabla (Medio + 1 .. Ultimo),


Valor,



else



Posición := Medio;

elsif Tabla (Medio) = Valor then

elseif Valor < Tabla (Medio) then



Posicion) ;



Posicion) ;

end Búsqueda_Binaria;



¿Qué es lo que sucedería?


end if;



(20)


(10,20,)


(10,20,30,40)

First:2 Last:2

Valor : 20

First:1 Last:2

First:1 Last:5


Valor : 20

Valor : 20


Pos:2

Pos:2

Pos:2



A la “ida” de la recursividad pasaremos el valor que buscamos la
posición del primero y la posición de medio-1. Cuando se encuentra el valor
buscado (“vuelta” de la recursividad) se va vaciando la pila con la posición en la
que se encuentra el valor buscado.


Hacer el ejercicio el problema iterativo

Resultado := Resultado + I;

for I in 1 .. 100 loop

end loop;


Resultado := 0;



procedure Programa is
Resultado := Integer := 0;

de forma recursiva.



4

Programación. Tema 5: Recursividad


(16/Mayo/2004)



procedure Calcula (I : in Integer

is

Resultado : in out Integer)



Procedimiento que de la vuelta a una lista. Lo haremos solo

cambiando los punteros.

-- Condiciòn de parada
if I > 100 then

return;
end if;
Resultado := Resultado + 1;
Calcula (I + 1, Resultado);



end Calcula;

begin



begin
Calcula (1, Resultado)
end Programa;



Lista.Primero := Anterior;
return;

if Actual /= null then


end if;
Invertir (Actual, Actual.Siguiente);
Actual.Siguiente := Anterior;

procedure Invertir (Anterior, Actual : T_Nodo_Ptr)
is
begin



end Invertir;


procedure Invertir_Lista (Lista : in out T_Lista) is



begin



end Invertir;



if Lista.Primero = null then

end if;
Invertir (null, Lista.Primero);

return;



5