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 pila al elemento anterior. Los programas recursivos tendrán casi siempre la siguiente estructura: ¾ Avance ¾ Condición de parada ¾ Procesamiento Se vera más claro con un ejemplo: procedure Escribir ( N : in Natural) is begin if N = 0 then return; end if; Int_IO.Put (N); Escribir (N – 1); Int_IO.Put (N); 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 321 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.

Escribir “3”

Escribir “2”

Escribir “1”

Algunos ejemplos de recursividad: ¾ 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. Frase : String (1 .. 4) := “Hola”; procedure Escribir (N : in Natural) is begin if N > Frase’Length then return; end if; Escribir (N + 1); Put (Frase (N)); end Escribir;

¿Qué es lo que sucedería? Escribir “A” En la pantalla veríamos Escribir “L”

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 return 1; else return N*Factorial (N-1); end if; end Factorial;

¿Qué es lo que sucedería?

Factorial (0)

1

Factorial (1)

1*1=1

Factorial (2)

2*1=2

Factorial (3)

3*2=6

Factorial (4)

4*6=24

Factorial (5)

Resultado 5*24=120

¾ Casi todos las funciones y procedimientos iterativos pueden realizarse con funciones o procedimientos recursivos; como por ejemplo la búsqueda binaria. procedure Búsqueda_Binaria (Tabla : in T_Tabla; Valor : in Integer; Posicion : in out Integer ) is Primero : Natural := Tabla’First; Ultimo : Natural := Tabla’Last; Mitad : Natural := (Primero + Ultimo)/ 2; begin if Tabla’Lenght then raise No_Encontrado;

3

Programación. Tema 5: Recursividad

(16/Mayo/2004)

elsif Tabla (Medio) = Valor then Posición := Medio; elseif Valor < Tabla (Medio) then Búsqueda_Binaria (Tabla (Primer .. Medio - 1), Valor, Posicion) ; else Búsqueda_Binaria (Tabla (Medio + 1 .. Ultimo), Valor, Posicion) ; end if; end Búsqueda_Binaria;

¿Qué es lo que sucedería?

(20)

First:2

Last:2

Valor : 20

Pos:2

(10,20,)

First:1

Last:2

Valor : 20

Pos:2

(10,20,30,40)

First:1

Last:5

Valor : 20

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 := 0; for I in 1 .. 100 loop Resultado := Resultado + I; end loop; de forma recursiva. procedure Programa is Resultado := Integer := 0;

4

Programación. Tema 5: Recursividad

(16/Mayo/2004)

procedure Calcula (I : in Integer Resultado : in out Integer) is begin -- Condiciòn de parada if I > 100 then return; end if; Resultado := Resultado + 1; Calcula (I + 1, Resultado); end Calcula; begin Calcula (1, Resultado) end Programa; ¾ Procedimiento que de la vuelta a una lista. Lo haremos solo cambiando los punteros. procedure Invertir_Lista (Lista : in out T_Lista) is procedure Invertir (Anterior, Actual : T_Nodo_Ptr) is begin if Actual /= null then Lista.Primero := Anterior; return; end if; Invertir (Actual, Actual.Siguiente); Actual.Siguiente := Anterior; end Invertir; begin if Lista.Primero = null then return; end if; Invertir (null, Lista.Primero); end Invertir;

5