Inmersión

Sucede con frecuencia que no es posible abordar directamente el diseño recursivo de una función f porque no se encuentra una descomposición adecuada de los datos.

En esos casos, una técnica que puede solucionar el diseño consiste en definir una función g, más general que f, con más parámetros y/o más resultados, que para ciertos valores de los nuevos parámetros calcula lo mismo que f. Diremos que hemos aplicado una inmersión de f en g. La función más general, g, se denomina función inmersora. Y la función original, f, se denomina función sumergida.

Para calcular la función original basta establecer el valor inicial de los nuevos parámetros que hacen que la función g se comporte como la función f.

Inmersión no final: Suma de los elementos de un vector

Vamos a ilustrarlo a través de un ejemplo sencillo.

Dado un vector A[1..n], con n>0, se pide diseñar una función recursiva que calcule la suma de los elementos del vector A

Su especificación formal es la siguiente.-

El diseño recursivo de SUMA no parece abordable directamente ya que tendríamos que “descomponer” el vector A en un vector más pequeño, y del mismo tipo, lo cual es contradictorio. Al hacerlo más pequeño, claramente estamos cambiando su tipo, con lo que no podríamos llamar recursivamente a SUMA.

Lo que sí que podemos añadir es un parámetro entero j y definir una función que calcule “la parte” de SUMA que se extiende de 1 a j.

Para llevar a cabo el diseño recursivo pedido vamos a aplicar la técnica de inmersión no final.

1.- Consiste en obtener R´ a partir de R a través de un proceso de sustitución simbólica, el cual consiste en sustituir expresiones o constantes por nuevas variables.

2.- Q´ se obtiene mediante la conjunción de Q y el dominio de la nueva variable, en nuestro ejemplo, j.

3.- Valor que debemos dar a j en la invocación a iSUMA para conseguir que iSUMA devuelva el mismo valor que SUMA.

lo que nos garantiza que: R’ $\wedge$ ( j = n ) $\longrightarrow$ R

Procedemos ya a realizar el análisis por casos de la función iSUMA.

Queremos calcular la suma de la sección del vector que va de 1 a j, esto es, iSUMA(A, j)

Suponemos conocida la suma de la sección del vector comprendida entre 1 y j -1, esto es, iSUMA(A,j-1)

En conclusión, iSUMA(A, j) = iSUMA(A, j -1) + A[ j ]

Dicho de otra forma, e = e´ + A[ j ]

El caso trivial se corresponde con j = 1, ya que 1 ≤ j ≤ n

Por tanto, estamos hablando de la sección del vector comprendida entre 1 y 1

siendo su valor asociado, A[1]

donde la llamada inicial a la función es: iSUMA(A,n)

Sustituir una constante por una variable

Procedemos ya a realizar el análisis por casos de la función iSUMA

Queremos calcular la suma de la sección del vector que va de j a n, esto es, iSUMA(A, j)

Suponemos conocida la suma de la sección del vector comprendida entre j+1 y n, esto es, iSUMA(A, j+1)

En conclusión, e = e´+ A[ j ] o iSUMA(A, j) = iSUMA(A, j +1) + A[ j ]

El caso trivial se corresponde con j = n, esto es, la sección del vector A[n..n] siendo su valor asociado, A[n]

Llamada inicial a la función: iSUMA(A, 1)

Dado un vector A[1..n], con n>0, se pide diseñar una función recursiva que calcule la suma de los elementos del vector A

Su especificación formal es la siguiente.-

donde la llamada inicial a la función es: iSUMA(A,n)

Si en lugar de sustituir n por j, sustituimos 1 por j en R, la función iSUMA resultante es la siguiente:

donde la llamada inicial a la función es: iSUMA(A,1)

Inmersión no final: Vector Capicúa

Dado un vector A[1..n] de enteros, con n>0, se pide diseñar una función recursiva que determine si dicho vector leído de izquierda a derecha es lo mismo que leído de derecha a izquierda (es o no capicúa)

Su especificación formal es la siguiente.-

El diseño recursivo de CAPICÚA no parece abordable directamente ya que tendríamos que “descomponer” el vector A en un vector más pequeño y del mismo tipo, lo cual es contradictorio. Al hacerlo más pequeño, claramente estamos cambiando su tipo, con lo que no podríamos llamar recursivamente a CAPICÚA .

Lo que sí que podemos añadir son dos parámetros enteros i y j y definir una función que calcule “la parte” de CAPICUA que se extiende de i a j.

Para llevar a cabo el diseño recursivo pedido vamos a aplicar la técnica de inmersión no final: Sustituimos 1 por i y n por j, determinamos el dominio de i y de j, así como los valores que debemos dar a i y j en la invocación a iCAPICUA para conseguir que iCAPICUA devuelva el mismo valor que CAPICUA.

Queremos calcular si la sección del vector que va de i a j es capicúa, esto es, iCAPICUA(A, i, j)

Suponemos conocida la suma de la sección del vector comprendida entre i+1 y j -1, esto es, conocemos iCAPICUA(A,i+1,j-1)

En conclusión, iCAPICUA(A, i, j) = iCAPICUA(A, i+1, j -1) AND (A[ i ] = A[ j ])

Los casos triviales corresponden secciones de tamaño 1 y 2, esto es, i = j e i = j - 1

Si i = j entonces el vector es capicúa y si i = j-1 dependerá de la comparación de A[i] y A[j]

La función iCAPICUA resultante es:

La llamada inicial a la función se realizará con i=1 y j=n, de ese modo.-

CAPICUA(A) = iCAPICUA(A, 1, n)

Vector capicúa (rango vacío)

Ejemplo propuesto: Media aritmética

Dado un vector A[1..n] de reales, con n>0, se pide diseñar una función recursiva que calcule la media aritmética de los elementos del vector

Ejemplo: Simetría de una matriz

Dada una matriz A[1..n][1..n], con n>0, se pide diseñar una función recursiva que determine si dicha matriz es simétrica o no

Su especificación formal es la siguiente.-

El diseño recursivo de SIMETRICA no parece abordable directamente ya que tendríamos que “descomponer” la matriz A en una matriz más pequeña y del mismo tipo, lo cual es contradictorio.

¿ SIMETRICA(A) ?

Vamos a añadir un parámetro entero k y definir una función que calcule “la parte” de SIMETRICA que se extiende desde la fila 1 a la fila k y de la columna 1 a la columna k

Para llevar a cabo el diseño recursivo pedido vamos a aplicar la técnica de inmersión no final: Sustituimos n por k, determinamos el dominio de k, así como los valores que debemos dar a k en la invocación a iSIMETRICA para conseguir que iSIMETRICA devuelva el mismo valor que SIMETRICA

¿ SIMETRICA(A,k) ?

Llamada inicial a la función: iSIMETRICA(A,n)

¿ iSIMETRICA(A,k) ?

Suponemos conocido iSIMETRICA(A,k-1)

iSIMETRICA(A,k) = iSIMETRICA(A,k-1) $\wedge$ (A[k][1]=A[1][k]) $\wedge$ (A[k][2]=A[2][k]) $\wedge$ … $\wedge$ (A[k][k-1]=A[k-1][k])

iSIMETRICA(A,k) = iSIMETRICA(A,k-1) $\wedge$ (A[k][1]=A[1][k]) $\wedge$ (A[k][2]=A[2][k]) $\wedge$ … $\wedge$ (A[k][k-1]=A[k-1][k])

iSIMETRICA(A,k) = iSIMETRICA(A,k-1) $\wedge$ (A[k][1]=A[1][k]) $\wedge$ (A[k][2]=A[2][k]) $\wedge$ … $\wedge$ (A[k][k-1]=A[k-1][k])

Q $\equiv$ { 2 ≤ k ≤ n }

Función Banda_Simetrica( A[1..n][1..n] : matriz de enteros;  k : entero) retorna  ( b : booleano )
     var i:entero, iguales:booleano fvar 
      i = 0
      iguales = VERDADERO
        mientras (i < k-1 AND iguales ) hacer
                  i = i + 1
                  si (A[k][i] == A[i][k]) entonces iguales=FALSO 
                  fsi
        fmientras
   retorna iguales
ffunción

R $\equiv$ { b = ($\forall$i) (A[ k ][ i ] = A[ i ][ k ] : 1 ≤ i ≤ k-1) }

Q $\equiv$ { 1 ≤ k ≤ n }

Función iSIMETRICA ( A[1..n][1..n]: matriz de enteros;  k : entero ) retorna  ( b : booleano )
   si  …  entonces retorna …
   sino retorna iSIMETRICA( A,k-1 ) AND Banda_Simetrica(A,k )
   fsi
ffunción

R` $\equiv$ { b = ($\forall$i) (($\forall$j) (A[ i ][ j ] = A[ j ][ i ] : 1 ≤ j ≤ k) : 1 ≤ i ≤ k)}

Llamada inicial a la función: iSIMETRICA(A,n)

El caso trivial se corresponde con k = 1, ya que 1 ≤ k ≤ n

Por tanto, estamos hablando de la sección de la matriz de 1 x 1

siendo su valor asociado, VERDADERO

Función iSIMETRICA ( A[1..n][1..n]: matriz de enteros;  k : entero ) retorna  ( b : booleano )
   si  k=1  entonces retorna VERDADERO
   sino retorna iSIMETRICA( A,k-1 ) AND Banda_Simetrica(A,k )
   fsi
ffunción

Ejercicio: Matriz cuyos elementos son el doble del situado a la izquierda

Dada una matriz A[1..n][1..m] de enteros, siendo n y m mayores que 0, se quiere diseñar una función recursiva que compruebe si todos los elementos cumplen que su valor es el doble del valor del elemento situado a su izquierda

Ejemplos:

Especificación formal.-

Q $\equiv$ { 1 ≤ n $\wedge$ 1 ≤ m}

Función MATRIZ_DOBLE ( A[1..n][1..m]: matriz de enteros) retorna ( b : booleano )

R $\equiv$ { b = ($\forall$i) (($\forall$j) ( 2 * A[ i ][ j-1 ] = A[ i ][ j ] : 2 ≤ j ≤ m) : 1 ≤ i ≤ n) }

¿ MATRIZ_DOBLE(A) ?

Sustituimos n por k (inducción sobre las filas de la matriz)

Q $\equiv$ { 1 ≤ k $\wedge$ 1 ≤ m}

Función iMATRIZ_DOBLE ( A[1..n][1..m]: matriz de enteros, k:entero) retorna ( b : booleano )

R $\equiv$ { b = ($\forall$i) (($\forall$j) ( 2 * A[ i ][ j-1 ] = A[ i ][ j ] : 2 ≤ j ≤ m) : 1 ≤ i ≤ k) }

¿ MATRIZ_DOBLE(A,k) ?

¿ iMATRIZ_DOBLE(A,k) ?

Suponemos conocido iMATRIZ_DOBLE(A,k-1)

iMATRIZ_DOBLE(A,k) = iMATRIZ_DOBLE(A,k-1) $\wedge$ AUX_DOBLE_FILAS(A,k)

¿ objetivo de AUX_DOBLE_FILAS(A,k) ? -> comprobar si todo elemento de la fila k es el doble del situado a su izquierda

Q $\equiv$ { 1 ≤ k $\wedge$ 1 ≤ m}

Función AUX_DOBLE_FILAS ( A[1..n][1..m]: matriz de enteros; k : entero ) retorna  ( b:booleano )
  var  j : entero, resultado : booleano fvar
  j = 1
  resultado = VERDADERO
  mientras ( j < m AND resultado )
      j = j + 1
      si ( 2*A[ k ][ j -1 ] != A[ k ][ j ] ) entonces   
          resultado = FALSO  
      fsi
  fmientras
  retorna resultado
ffunción

R $\equiv$ { b = ($\forall$j) ( 2 * A[ i ][ j-1 ] = A[ i ][ j ] : 2 ≤ j ≤ m) }

Q $\equiv$ { 1 ≤ k $\wedge$ 1 ≤ m}

Función iMATRIZ_DOBLE ( A[1..n][1..m]: matriz de enteros; k : entero ) retorna (b:booleano)
   si  …  entonces …
   sino retorna iMATRIZ_DOBLE(A,k-1) AND AUX_DOBLE_FILAS(A,k )
   fsi
ffunción

R $\equiv$ { b = ($\forall$i) (($\forall$j) ( 2 * A[ i ][ j-1 ] = A[ i ][ j ] : 2 ≤ j ≤ m) : 1 ≤ i ≤ k) }

Llamada inicial a la función: iMATRIZ_DOBLE(A,n)

El caso trivial se corresponde con k = 1, ya que 1 ≤ k ≤ n

Por tanto, estamos hablando de la sección de la matriz de 1 x m

siendo su valor asociado, AUX_DOBLE_FILAS(A,1)

Función iMATRIZ_DOBLE ( A[1..n][1..m]: matriz de enteros; k : entero ) retorna (b:booleano)
   si  k=1  entonces AUX_DOBLE_FILAS(A,k)
   sino retorna iMATRIZ_DOBLE(A,k-1) AND AUX_DOBLE_FILAS(A,k )
   fsi
ffunción

Ejercicio propuesto: Filas orden estrictamente decreciente

Dada una matriz A[1..n][1..m] siendo n y m mayores que 0, dicha función tiene que comprobar si los elementos de cada fila, leídos de izquierda a derecha, están en orden estrictamente decreciente. La inducción se ha de realizar sobre las columnas de la matriz.

Ejemplos:

Ejercicio propuesto: Tableros

Calcular el número de formas diferentes de colocar un tablero de m x m sobre otro de n x n donde n ≥ m, n > 0 y m > 0

Ejercicio propuesto: Rayuela

Dados unos cuadros alineados (como si se tratara del juego de la rayuela) y numerados desde el 0, el juego comienza en el cuadro 0 y consiste en ir saltando hasta el cuadro que ocupa la posición n, siendo n>0, permitiéndose para ello dos posibles movimientos:

Salto de longitud 1

Salto de longitud 2

Se desea diseñar una función recursiva que calcule de cuántas maneras diferentes se puede llegar al n-ésimo cuadro desde el cuadro de partida (numerado con el 0)

Ejercicio propuesto: Plano

Dado un plano n x n y dado un punto (x,y), con x>0 $\wedge$ y>0, en el plano, se desea saber cuántos caminos diferentes pueden llevarnos desde el origen (0,0) al punto (x,y) teniendo en cuenta que no se admiten retrocesos en el desplazamiento. Los únicos movimientos permitidos son a la derecha y hacia arriba en vertical, siendo dichos movimientos de longitud 1.