Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Guías prácticas/Recursividad/Solución al ejercicio 5 de recursividad

De Wikilibros, la colección de libros de texto de contenido libre.
1.
 public class Imagen {
   private char matriz[][];
   private int tamX;
   private int tamY;
   
   public Imagen(char entrada[]) {
     super();
     int i,j,k;
     tamX=(int) Math.sqrt(entrada.length);
     tamY=tamX;
     matriz=new char[tamX][tamY];
     for(i=0,k=0;i<tamX;i++)
       for(j=0;j<tamY;j++,k++)
         matriz[i][j]=entrada[k];
   }
   
   public Imagen(char entrada[], int tamX, int tamY) {
     super();
     int i,j,k;
     this.tamX=tamX;
     this.tamY=tamY;
     matriz=new char[tamX][tamY];
     for(i=0,k=0;i<tamX;i++)
       for(j=0;j<tamY;j++,k++)
         matriz[i][j]=entrada[k];
   }

   public void show()
   {
     int i,j;
     for(i=0;i<tamX;i++)
     {
       for(j=0;j<tamY;j++)
       {
         System.out.print(matriz[i][j]);
         System.out.print(";");
       }
       System.out.println();
     }
   }
2.
 private void pintarRecursivo(char color,int x, int y,char colorOriginal)
 {
   int i,j,a,b;
   
   if(matriz[x][y]!=colorOriginal) return;
   if(matriz[x][y]==color) return;
   
   matriz[x][y]=color;
   
   if(x>0) pintarRecursivo(color,x-1,y,colorOriginal);
   if(y>0) pintarRecursivo(color,x,y-1,colorOriginal);
   if(x<(tamX-1)) pintarRecursivo(color,x+1,y,colorOriginal);
   if(y<(tamY-1)) pintarRecursivo(color,x,y+1,colorOriginal);  
 }
   
   public void pintar(char color,int x, int y)
   {
     pintarRecursivo(color,x,y,matriz[x][y]);
   }

La cota de la complejidad del algoritmo está dada por:

En este caso, k es 4 en el peor de los casos, y la profundidad máxima es el máximo entre el ancho y el alto de la imagen, que en el peor de los casos (una línea de píxeles) es n, de manera que:

Observando el código y evaluando el peor caso punto por punto, se obtiene una cota de la complejidad del algoritmo, pero es obvio que esta cota puede mejorarse mucho. Analizando el comportamiento de este algoritmo, se puede tener una idea más precisa del orden de su complejidad: Por cada punto sobre el cual se corra el algoritmo, se generarán 4 llamados recursivos; éstos generarán 4 llamados recursivos, pero uno de ellos será sobre el punto anteriormente pintado, el cual no generará sucesivos llamados. Así, como se ve en la figura, al cabo de dos llamados recursivos, los puntos sobre los que se generan llamadas recursivas quedarán fuera del alcance del punto original, de manera que por cada punto, se preguntará por su color a lo sumo 5 veces, es decir, que el orden de la complejidad de este algoritmo es lineal – .

3.
 private void pintarIterativo(char color,int x, int y,char colorOriginal)
 {
   int i,j,a,b;
   Punto p=new Punto(x,y);
   Stack s=new Stack();
   s.push(p);
   
   while(!s.isEmpty())
   {
   p=(Punto)s.pop();
     
   if(matriz[p.getX()][p.getY()]!=colorOriginal) continue;
   if(matriz[p.getX()][p.getY()]==color) continue;
   
   matriz[p.getX()][p.getY()]=color;
   if(p.getX()>0) s.push(new Punto(p.getX()-1,p.getY()));
   if(p.getY()>0) s.push(new Punto(p.getX(),p.getY()-1));
   if(p.getX()<(tamX-1)) s.push(new Punto(p.getX()+1,p.getY()));
   if(p.getY()<(tamY-1)) s.push(new Punto(p.getX(),p.getY()+1));
   }
 }

 public void pintar(char color,int x, int y)
 {
   pintarIterativo(color,x,y,matriz[x][y]);
 }

En este caso, el análisis de la complejidad se hace mucho más complicado mirando el código: consiste de un solo ciclo, cuya condición de terminación depende del comportamiento del algoritmo, por lo que me parece que la mejor opción es revisar este último. Ya que esta versión iterativa reproduce el comportamiento de la versión recursiva del algoritmo, el análisis será idéntico, al igual que la conclusión.