Diseño de programas recursivos

• Un subprograma (procedimiento o función) es recursivo cuando en su definición aparece una (o más) llamada a sí mismo.

• El fundamento de la construcción de subprogramas recursivos consiste en suponer que ya se dispone del propio subprograma que se quiere desarrollar, durante la definición de éste. ( "Principio de Inducción"

• Los casos triviales definen la solución directamente y los casos "más complicados" se definen utilizando una (o más) llamadas al subprograma que se define.

Descomponer el problema en SUBproblemas

MISMO TIPO pero MENOR TAMAÑO

(

Tipo(PROBLEMA) == Tipo(SUBproblema)

Ejemplo. Función recursiva para el cálculo del factorial.

Ejercicio. Construir un procedimiento recursivo para el cálculo del factorial.

Coste del algoritmo recursivo

• opción1: factorial(n) se resuelve con n+1 llamadas

• las n primeras llamadas, tienen un coste c1.

• la última llamada tiene un coste c2.

Etapas en el diseño de programas recursivos

1. ESPECIFICACION/PARAMETRIZACIÓN

• Determinar los parámetros (fundamental para el diseño)

• Definir qué hace el algoritmo en función de esos parámetros (qué resuelve cada subproblema)

• Establecer cuál será la llamada inicial: parámetros IN, IN OUT y OUT.

2. ANALISIS DE LOS CASOS

TRIVIALES: Determinar para qué valores de los parámetros (bajo qué condiciones), existe una solución directa y cuál es esa solución. Debe existir como mínimo 1 caso trivial, si no el algoritmo no parará de generar subproblemas.

GENERALES: Determinar para qué valores de los parámetros la solución se obtiene por descomposición en subproblemas del mismo tipo. Establecer cómo se calculan las soluciones resueltas las llamadas recursivas correspondientes.

Comprobar que las llamadas recursivas usan exactamente los parámetros definidos y que el tamaño del problema se reduce o tiende hacia los casos triviales.

3. DISEÑO DEL ALGORITMO ( y quizás las estructuras de datos)

• Agrupar lo diseñado en pasos previos, procurando simplificar el algoritmo cuando sea posible.

• Eliminar redundancias y agrupar casos triviales cuando sea interesante.

• Procurar la eliminación de cálculos repetidos originada por el estudio separado de casos.

4. IMPLEMENTACION

• Implementar las estructuras de datos, adecuadas a la representación de los mismos.

• Construir el subprograma (procedimiento o función) recursivo (en Ada en nuestro caso).

Ejemplo: Búsqueda dicotómica

( Entrada: un elemento e de tipo t_elemento y

una tabla t de elementos de tipo t_elemento

Salida: un booleano

( Pre: un elemento e de tipo t_elemento y

Post: cierto sii el elemento e aparece en t

ANÁLISIS DE CASOS

( TRIVIALES:

La tabla está vacía, ( falso.

El elemento e coincide con el central de la tabla, (cierto.

( GENERALES:

El elemento e ES MENOR que el central de la tabla, ( esta?(e, mitad_izq_tabla).

El elemento e ES MAYOR que el central de la tabla, ( esta?(e, mitad_dch_tabla).

DISEÑO DE ALGORITMOS

esta?(e, t)

si vacía(t), falso

sinosi t(mitad)=e, cierto

sinosi t(mitad)>e, esta?(e, mitad_izq(t))

sino esta?(e, mitad_dch(t))

Ejemplos de subprograma recursivo

Ejemplo1: Torres de Hanoi

Se tienen 3 barras y n discos (con n>0), todos los discos de diferentes tamaños. Inicialmente los discos están colocados en una barra formando una pirámide (el mas grande está en la base y el más pequeño en la cima). El objetivo es obtener la secuencia de movimientos que permitirán mover la pirámide de una barra a otra respetando las siguientes restricciones:

• En un paso se puede mover solo un disco de una barra a otra.

• No se puede colocar un disco encima de otro más pequeño.

Estudio y comprensión del problema

ESPECIFICACIÓN/PARAMETRIZACIÓN

• Entrada: N altura de la torre a trasladar y barras implicadas (1, 2 y 3).

Salida:Secuencia de movimientos de la forma mueve de nombre barra a nombre barra

• Pre: (N>0)

Post: La secuencia de salida describe ordenadamente los movimientos que se deben realizar para llevar la torre del origen al destino indicados

• Hanoi(N, inicial, auxiliar, final)

ANÁLISIS DE CASOS

N=1, mueve de barra inicial a barra final

N > 1

• obtener secuencia de movimientos para mover los N-1 discos desde la barra inicial a la barra auxiliar.

• mueve de barra inicial a barra final

• obtener secuencia de movimientos para mover los N-1 discos desde la barra auxiliar a la barra final.

DISEÑO DE ALGORITMOS

subprograma hanoi (altura, inicial, auxiliar, final)

Entrada: altura de la torre a trasladar (integer) y barras implicadas (1, 2 y 3).

Precondiciones: altura >0.

Salida: Secuencia de movimientos (mueve de barra_i a barra_j)

IMPLEMENTACIÓN

Ejercicio. Simular la ejecución de la llamada al procedimiento hanoi(3, 1, 2, 3). ¿Que resultado se obtiene? ¿Cuántas veces es invocado el procedimiento hanoi? ¿Cuantas veces sería invocado el procedimiento hanoi como consecuencia de la ejecución de hanoi(4, 1, 2, 3)? ¿Cuantos movimientos se obtendrían?

Ejemplo2: Monedas a devolver

Se desea diseñar un subprograma recursivo que tomando como entrada una cantidad mayor o igual que 0 y un conjunto de tipos de monedas, devuelva dicha cantidad de manera que el número de monedas sea el mínimo posible.

ESPECIFICACIÓN/PARAMETRIZACIÓN

• Entrada:

Cantidad y Cjto. de tipos de moneda

Salida: Lista de pares (ni,mi) donde ni indica el número de monedas de tipo mi a devolver

• Pre: Cantidad>0

Post: El número de monedas devueltas será el menor posible.

• Pagar(cantidad, conjunto_monedas)

ANÁLISIS DE CASOS

• casos TRIVIALES (sin recursión). Si el Cjto. de tipos de moneda sólo tiene un tipo de monedas m, habrá que devolver (n, m). Donde n es el cociente de la división de la cantidad entre el valor de m.

– casos GENERALES (recursión). Si el Cjto. de tipos de moneda tiene más de un tipo de monedas, (1) Se devuelve el par (n,m) ,correspondiente al mayor número posible de monedas del valor más alto y (2) Se devuelven los cambios de la cantidad restante con las monedas del subconjunto obtenido tras eliminar la moneda de valor más alto

(

Diseño de algoritmos

Entrada: cantidad y un cjto. de tipos de moneda

Salida: lista de pares (número, tipo de moneda)

subprograma Pagar( cantidad, cjto de monedas)

escribir (moneda mayor del cjto, cantidad división_entera moneda mayor cjto)

si hay más tipos de moneda en el conjunto,

Pagar ( cantidad_restante, subcjto. de tipos de moneda)

fin subprograma

donde

cantidad_restante es:

cantidad – moneda mayor conjunto* (cantidad división_entera moneda mayor cjto)

subcjto. De tipos monedas es:

cjto. de monedas – moneda mayor conjunto

IMPLEMENTACIÓN

Por un lado, se selecciona una representación para los tipos de datos que intervienen.

Cantidad: natural

Conjunto de monedas: t_monedas

type t_monedas is

(peseta, duro, diez, cinco_duros, cincuenta, veinte_duros,

doscientas, quinientas);

valor_moneda: constant array(t_monedas) of natural :=

(1, 5, 10, 25, 50, 100, 200, 500);

procedure pagar(cantidad:natural; moneda_mayor:t_monedas) is

resto, cociente: natural;

begin

— Obtener el número de monedas

cociente:= cantidad / valor_moneda(moneda_mayor);

— Obtener la cantidad restante

resto:= cantidad rem valor_moneda(moneda_mayor);

( — Escribir el par (ni,mi)

put(cociente); put(" moneda/s de ");

put(valor_moneda(moneda_mayor)); new_line;

end pagar;

Ejercicios

1. Sobre el ejercicio anterior realizar las siguientes propuestas:

• Simulación de pagar 311. ¿quinientas?

• Explicar el comportamiento del procedimiento pagar si la parte marcada precediera a las instrucciones de escritura.

• Simulación, tras el cambio anterior, de pagar 311.

• Modificar el programa para que trabaje con el siguiente conjunto de monedas (peseta, duro, cinco_duros y cincuenta).

• Dar un procedimiento iterativo equivalente a "cambios".

• ¿Qué efecto tendría añadir un caso trivial más con: if cantidadultimo then raise ERROR_EN_X;

  elsif elemento=lista(central) then return central;

  elsif elementob>then return X(lista,elemento,primero,central-1);

  else return X(lista,elemento,central+1,ultimo);

  end if;

  end X;

  sabiendo que: type t_elemento is … — (puede ser integer, character, string …)

  type t_rango is integer range 1..n;

  type t_lista is array(t_rango) of t_elemento;

  3. La idea de algoritmo que implementa el subprograma recursivo anterior se puede realizar de manera iterativa muy fácilmente. Diseña dicho algortimo iterativo y comenta con cuál de las 2 soluciones (recursiva o iterativa) te quedarías en función de las argumentaciones que se hacen al final del tema.

  Ejemplo3: Ordenación por fusión

  ESPECIFICACIÓN/PARAMETRIZACIÓN

  • Entrada: vector de enteros, V

  Salida: vector de enteros, V

  • Pre:

  Post: V tiene los mismos elementos que en la entrada pero ordenados de modo NO DECRECIENTE, esto es t(i) segundo(V), permutar(V) fin si

  sino si V tiene más de 2 elementos,

  mitad1(V, U), Merge_Sort(U),

  mitad2(V, T), Merge_Sort(T),

  Fusionar(U, T, V)

  IMPLEMENTAR

  type t_vector is array (natural range ) of integer;

  procedure Merge_Sort( V: in out t_vector) is

  procedure Fusionar (U T V ) is

  …

  end Fusionar;

  med: integer:= (V"first+V"last)/2; aux: integer;

  U: t_vector(V"first..med); T:t_vector(med+1..V"last);

  begin

  if V"first+1= V"last then

  if V(V"first)> V(V"last) then

  aux:= V(V"first);

  V(V"first):= V(V"last);

  V(V"last):= aux;

  end if;

  elsif V"first+1< V"last then

  U:= V(V"first.. med);

  T:= V(med+1.. V"last);

  Merge_Sort(U);

  Merge_Sort(T);

  Fusionar(U, T, V);

  end if;

  end Merge_Sort;

  Completa el ejemplo anterior con los siguiente ejercicios:

  • 1. Implementar el procedimiento de Fusión de dos vectores ordenados en un tercer vector.

  • 2. Calcular el coste de dicho algoritmo de Fusion.

  • 3. Calcular el coste del algoritmo Merge_Sort, formulando su recurrencia.

  • 4. Implementar el algoritmo de ordenación por selección y calcular su coste.

  Recursión e iteración

  ITERACION: Un proceso se repite por estar colocado dentro de una estructura cíclica.

  RECURSION: La ejecución de un subprograma se repite por medio de llamadas a sí mismo. Una (o más) sentencia condicional(es) controla las sucesivas llamadas.

  

  Existen clases de problemas (como es el caso de Fibonacci) cuya solución recursiva llevará aparejada graves problemas de eficiencia debido a que las llamadas recursivas acaban resolviendo un número importante de veces el mismo problema.

  Ejemplo

  

  Ejercicios

  • 1) Implementar los siguientes subprogramas en Ada de forma recursiva:

  function Exponencial(N,M:Natural) return Natural is

  –pre:

  –post: Exponecial(N,M) = NM

  procedure Exponencial(N,M:Natural; Resultado: out Natural) is

  –pre:

  –post: Resultado = NM

  • 2) Hacer un programa recursivo en Ada de forma que reciba desde la entrada externa (teclado), una serie de caracteres que acaban en punto y devuelva en la salida externa (pantalla) todo el texto pero al revés, comenzando por el punto final.

  • 3) Hacer un procedimiento en Ada con la siguiente especifiación:

  procedure Dar_la_vuelta ( S:String; Resultado: out String) is

  –pre:

  –post: Resultado es la palabra S dada la vuelta

  • 4) Tenemos la siguiente declaración de tipo

  

  • Se pide también la implementación de las mismas operaciones, pero usando procedimientos recursivos en vez de funciones.

  • ¿Cómo modificarías el programa Esta_Dicotómica, para que te diera como resultado un valor entero que corresponda al índice de la lista donde se ha encontrado el elemento buscado, o un valor Integer´last si ese elemento no está en la lista.

  • 5) La ejecución del procedimiento Dib_cuadrado produce el dibujo de un cuadrado, centrado en un punto predeterminado, cuya longitud de lado viene representada por el primer parámetro y la orientación = true indica que se debe dibujar sobre su base y orientación = false sobre su vértice. Ejemplo:

  

  • 6) Diseña e implementa un algoritmo recursivo que dados dos naturales N y M que verifican que M ( N, escriba en la salida externa (pantalla) los divisores de N que son mayores o iguales a M;

  • 7) Diseña e implementa un algoritmo recursivo que decida si un número es perfecto. Un número, N, es perfecto si la suma de todos sus divisores, excepto N, es exactamente N;

  • 8) Diseña e implementa un algoritmo recursivo que dada una matriz cuadrada de tamaño NxN, decida si la matriz es simétrica o no;

  • 9) Diseña e implementa un algoritmo recursivo que tomando como entrada una cantidad mayor o igual a 0 y un conjunto de tipos de monedas, devuelva la distribución de la cantidad entre los tipos de monedas, de manera que el número de monedas sea el mínimo posible.

  • 10) Dados los naturales N y S, diseñar un algoritmo recursivo que calcule al número de secuencias distintas de N dígitos binarios que contengan exactamente S 1"s. Lo mismo pero pudiendo aparecer cualquier dígito de 0 a 9.

  • 11) Diseñar un algoritmo recursivo que obtenga el número de caminos posibles que conectan dos puntos del plano (O y P), teniendo en cuenta que los desplazamientos posibles son dar un paso a la derecha y dar un paso hacia arriba.

  • 12) Supongamos que las losas de una calle están numeradas a partir de 0 y que los niños juegan a cruzar la calle haciendo dos tipos de movimientos: pasando de una losa a la siguiente o saltando por encima de una losa. Al principio del juego se colocan en la losa 0. Diseñar un algoritmo recursivo que calcule el número de caminos distintos que puedan seguirse para llegar exactamente a la losa N.

  

  • 13) A partir de un vector, T, de tipo Lista_Naturales y una posición, p, T´first ( p ( T"last, se desea determinar el número de saltos sucesivos necesarios para, partiendo de p, sobrepasar la última posición del vector. El valor T(i) (tened en cuenta que siempre es positivo) determina la longitud del salto a efectuar desde la posición i. Por ejemplo, siendo p = 2 y T = (5, 2, 4, 1, 3, 6)

  el número de saltos es 3. Diseñar un algoritmo recursivo que dados T y p determine el número de saltos.

  • 14) Averiguar que hacen los siguientes subprogramas:

  

  • 15) Se pide diseñar un algoritmo recursivo que, dado un natural N > 0, escriba en la salida externa todas las permutaciones con repetición de N elementos tomados de N en N. Ejemplo: si N = 2, aparecerán en pantalla los pares (1,1), (1,2), (2,1), (2,2). Se pide su implementación en Ada de forma recursiva.

   

  Enviado por:

  Pablo Turmero