Iterando por una matriz cuadrada recursivamente
Junio 5 2009 :: Algoritmia, Estructuras de datos, Java, Lógica ::
En otro ejercicio de la facultad se me pedía sumar todos los valores individuales de una matriz cuadrada a través de un algoritmo recursivo. Mi resolución en Java fue la siguiente:
public static int sumaMatriz(int arr2[][], int m, int n) {
if( (m == n) && (m == 0) ) return arr2[m][n];
if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a
if(m > n) {
if(n > 0) {
return arr2[m][n] + sumaMatriz(arr2, m, n-1); //Caso b
} else {
return arr2[m][n];
}
} else { //n > m
if(m > 0) {
return arr2[m][n] + sumaMatriz(arr2, m-1, n); //Caso c
} else {
return arr2[m][n];
}
}
}
Me interesa este ejercicio para pensar de otra forma sobre corrección de programas. La pregunta es si el algoritmo es correcto y después de pensarlo un poco llegue a la conclusión de que lo era. Por lo pronto para hacer una demostración formal debería usar inducción estructural pero este post trata más bien sobre trabajo previo a una demostración, lo que en How to Prove it llaman scratchwork. O sea el razonamiento a través del cual se llega a una demostración.
Primero que nada hagamos un poco de debugging con un caso simple de una matriz de 3×3. Para esto agregamos lo siguiente al código anterior:
public static int sumaMatriz(int arr2[][], int m, int n) {
if( (m == n) && (m == 0) ) return arr2[m][n];
System.out.println(n + ” ” + m);
if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a
if(m > n) {
….
….
Y testeamos la función llamándola con:
public class TP4 {
public static void main (String[] args) {
int[][] arr2;
arr2 = new int[3][3];
arr2[0][0] = 1;
arr2[0][1] = 2;
arr2[0][2] = 2;
arr2[1][0] = 4;
arr2[1][1] = 2;
arr2[1][2] = 3;
arr2[2][0] = 4;
arr2[2][1] = 7;
arr2[2][2] = 8;
System.out.println(”Ej9:”);
System.out.println( TP4.sumaMatriz(arr2,2 ,2));
}
}
Lo que muestra por consola es:
Ej9:
2 2
2 1
2 0
1 1
1 0
0 0
0 1
1 2
0 2
33
Podemos ver que todos los elementos de la matriz fueron accedidos y que el resultado es el correcto. Ahora imaginémonos el árbol de las llamadas de función.
Vemos que los elementos de la diagonal principal hacen 3 llamados más, al próximo elemento de la diagonal principal, y a los dos elementos con m o n decrementados en uno. Mientras que los elementos que no están en la diagonal principal hacen un solo llamado.
Razonamiento (Informal) sobre la corrección del Algoritmo
Consideremos una matriz cuadrada de grado m, tal que m sea mayor que 5 (esto es por claridad para hacer este ejercicio) y concentrémonos en los últimos 5×5 casilleros del limite inferior derecho, que es donde comienza el algoritmo.
Primer paso toma el elemento en m x m:
A partir de esto se realiza la llamada recursiva:
if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a
De la que se desprenden los siguientes 3 pasos.
El caso b:
return arr2[m][n] + sumaMatriz(arr2, m, n-1); //Caso b
De nuevo el caso a:
if(m == n) return arr2[m][n] + sumaMatriz(arr2, m-1, n) + sumaMatriz(arr2, m-1, n-1) + sumaMatriz(arr2, m, n-1); //Caso a
Y finalmente el caso c:
return arr2[m][n] + sumaMatriz(arr2, m-1, n); //Caso c
Hemos llegado a llenar una matriz de 3×3, pero esto no nos demuestra nada, ahora lo interesante es saber que pasa cuando continua el algoritmo en los pasos siguientes y aquí es donde esta el truco.
Lo interesante es que las 3 posibles llamadas recursivas garantizan la siguiente:
Por el caso a, desde una llamada de la función desde un casillero en la diagonal principal, no se llamara a la función en ningún casillero que este en la misma linea o columna de los elemento de donde han sido llamados por un casillero en la diagonal principal anterior.También por el caso a, la iteración a través de elementos de la diagonal principal eventualmente cubrirá todos los elementos de la diagonal principal de la matriz.
Por el caso b, desde una llamada de la función desde un casillero en una columna que no sea en la diagonal principal, siempre continuara por esa misma columna hasta completarla.
Por el caso c, desde una llamada de la función desde un casillero en la fila que no sea en la diagonal principal, siempre continuara por esa misma fila hasta completarla.
A partir de esto podemos inferir que el algoritmo pasa por todos los elementos de cualquier matriz cuadrada.
Importante
Quiero recalcar que esto es un razonamiento, a partir del cual por inducción estructural podría construirse una demostración, pero en términos de lógica formal no es una demostración. Igual, no deja de ser un razonamiento valido, lo cierto es que en la programación como practica es importante poder pensar si lo que se esta haciendo es correcto y si los programas que uno hace cumplen con las necesidades que uno tiene, pero también es cierto que sería completamente Overkill el tener que hacer una demostración formal de cada programa que uno hace. Lo importante es tener herramientas para poder razonar y pensar sobre como se programa.
