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 3 de recursividad

Clase patrón

 public class Patron {
   int x;
   int y;
   int L;

   public int solucionRecursiva(int lado,int xCentro,int yCentro);
   public int solucionIterativa(int lado,int xCentro,int yCentro);
     
   public Patron(int x,int y,int L)
   {
     this.x=x;
     this.y=y;
     this.L=L;
   }
 }

El método recursivo

 public int solucionRecursiva(int lado,int xCentro,int yCentro)
 {
   int dentro=0;
   if (x<=xCentro+lado/2&&x>=xCentro-lado/2&&
     y<=yCentro+lado/2&&y>=yCentro-lado/2)
       dentro=1;
   if (lado<=2)  //caso base
     return dentro;
   //caso recursivo
   return dentro+
     solucionRecursiva(lado/2,xCentro+lado/2,yCentro+lado/2)+
     solucionRecursiva(lado/2,xCentro+lado/2,yCentro-lado/2)+
     solucionRecursiva(lado/2,xCentro-lado/2,yCentro+lado/2)+
     solucionRecursiva(lado/2,xCentro-lado/2,yCentro-lado/2);
 }

La complejidad del método

En este caso, el algoritmo abre 4 hijos, pero y la complejidad general para un algoritmo que abra n hijos es:

$C={\cfrac {n^{h+1}-1}{n-1}}$

En nuestro caso es:

$C={\cfrac {4^{h+1}-1}{4-1}}$

Para h niveles, ahora, la cuestión es determinar la cantidad de niveles en el peor de los casos. La profundidad total del árbol de llamadas recursivas estará dado por la cantidad de veces que se puede dividir el cuadrado. Como el ancho de los cuadraditos está acotado, y en cada paso se divide por dos el ancho del cuadrado original:

${\frac {a}{2^{m}}}=2$

Siendo $m$ la cantidad máxima de veces que se puede dividir el cuadrado. Por lo tanto:

$a=2^{m+1}$

$log_{2}a=m+1$

Y la complejidad del algoritmo en el peor caso queda:

$C={\cfrac {4^{log_{2}a}-1}{3}}$

$C={\cfrac {(2*2)^{log_{2}a}-1}{3}}$

$C={\cfrac {2^{log_{2}a}*2^{log_{2}a}-1}{3}}$

$C={\cfrac {a*a-1}{3}}$

$C={\cfrac {a^{2}-1}{3}}$

El orden de la complejidad del algoritmo queda entonces en función del ancho del cuadrado de entrada, y resulta de $O(a^{2})$.

Transformación del método recursivo en iterativo

 public int solucionIterativa(int lado,int xCentro,int yCentro)
 {
   int cuenta=0;
   Stack cuadradosAProcesar;
   cuadradosAProcesar=new Stack();
   cuadrado primero=new cuadrado(lado,xCentro,yCentro);
   cuadrado actual;
   cuadradosAProcesar.push(primero);
   while (!cuadradosAProcesar.isEmpty())
   {
     actual=(cuadrado)cuadradosAProcesar.pop();
     if(x<=actual.getX()+actual.getLado()/2&&
      x>=actual.getX()-actual.lado/2&&
      y<=actual.getY()+actual.getLado()/2&&
      y>=actual.getY()-actual.getLado()/2)
         cuenta++;
     if(actual.getLado()>2)
     {
       cuadradosAProcesar.push(
           new cuadrado(actual.getLado()/2,
                        actual.getX()+actual.getLado()/2,
                        actual.getY()+actual.getLado()/2));
       cuadradosAProcesar.push(
           new cuadrado(actual.getLado()/2,
                        actual.getX()+actual.getLado()/2,
                        actual.getY()-actual.getLado()/2));
       cuadradosAProcesar.push(
           new cuadrado(actual.getLado()/2,
                        actual.getX()-actual.getLado()/2,
                        actual.getY()+actual.getLado()/2));
       cuadradosAProcesar.push(
           new cuadrado(actual.getLado()/2,
                        actual.getX()-actual.getLado()/2,
                        actual.getY()-actual.getLado()/2));
     }      
   }
   return cuenta;
 }