Fallo java.lang.StackOverflowError

[Kyokatallama]

Buenas,

Antes de nada un saludo a todo el foro. Espero que la duda que traigo me haya servido para iniciarme en vuestra comunidad y espero poder aportar mis escasos conocimientos a toda esta familia.

Estoy realizando un programa en Java que a través de un fichero de entrada de las dimensiones de una serie de edificios, me devuelva un fichero de salida en el que se especifique el Skyline (visión desde el horizonte) de estos edificios.

Os detallo el código para que podáis echarme una cable:

temp = ciudad.size();
DyV(ciudad, 0, temp, linea);
}

public static void DyV(ArrayList<edificio> c, int i, int j, ArrayList<TipoSkyline> s) {

int m,n;
ArrayList<TipoSkyline> s1 = new ArrayList<TipoSkyline>();
ArrayList<TipoSkyline> s2 = new ArrayList<TipoSkyline>();

m = (i + j - 1)/2;
n = j - i + 1;

s1 = new ArrayList<TipoSkyline>();
s2 = new ArrayList<TipoSkyline>();

if (n == 1) {
s.add(new TipoSkyline(Integer.valueOf(c.get(0).getInicio()), (Integer.valueOf(c.get(0).getAltura()))));
}
else; {
DyV(c, i, m, s1);
DyV(c, m+1, j, s2);
Combinar(s1, s2, s);
}
}

El problema viene en la creación del objeto s1 y s2 (new Tiposkyline...) y a las 2 llamadas recursivas a DyV...
Ambas me devuelven error "java.lang.StackOverflowError".

Entiendo que son errores por llamadas recursivas infinitas. Pero tambien en la creación del objeto s1 y s2??
No tengo un caso base bien creado (n == 1) que evita esas llamadas recursivas infinitas??

Gracias anticipadas por todo y un saludo.
Elias.

[CapacProg]

Veo que, que construyes dos veces s1, s2.
Si no tienes un caso para n==1, que es la condición de finalización para la recursividad, no creo que podamos ayudarte si no sabemos ni de lo que tratas de implementar. Debes de revisar tu algoritmo y en si ver lo que falta probando para diferentes casos.
Como reza el dicho "Si tu no puedes, no creas que la máquina lo hará por ti" .

[Kyokatallama]

Mmmmm... La construcción doble se debe a que estaba probando diferentes cosas y olvidé devolverlo a su estado original... :P.

Disculpa, puedes eliminar cualquiera de ellas...


Para n == 1 (caso base) defino:

if (n == 1) {
s.add(new TipoSkyline(Integer.valueOf(c.get(0).getInicio()), (Integer.valueOf(c.get(0).getAltura()))));
}

Para el resto de casos:
else; {
DyV(c, i, m, s1);
DyV(c, m+1, j, s2);
Combinar(s1, s2, s);
}


El algoritmo que intento implementar es un Divide y Venceras.

El main del programa define variables, lee de un archivo de entrada mediante un scanner (fin) y lo mete en una variable ciudad (que contiene el conjunto de edificios). Linea, contendrá la un arralist de salida con el dibujo del skyline.

Los edificios están definidos como clases de 3 parámetros: inicio, fin y altura.
Mientras que la clase TipoSkyline viene definido por 2:Cambio y altura. (Donde cambio indica el punto en que cambia de altura el Skyline).

public static void main(String[] args) throws IOException {
String[] edificio;
ArrayList<edificio> ciudad = new ArrayList<edificio>();
ArrayList<TipoSkyline> linea = new ArrayList<TipoSkyline>();
int temp;

Scanner fin = new Scanner(new File("src/skyline.in"));

while (fin.hasNextLine()) {
String line = fin.nextLine();
edificio = line.split(" ");
ciudad.add(new edificio(Integer.valueOf(edificio[0]),Integer.valueOf(edificio[1]),Integer.valueOf(edificio[2])));
}

temp = ciudad.size();
//LLAMADA INICIAL DEL ALGORITMO RECURSIVO.
DyV(ciudad, 0, temp, linea);
}
Por otro lado, DyV:

public static void DyV(ArrayList<edificio> c, int i, int j, ArrayList<TipoSkyline> s) {

int m,n;
ArrayList<TipoSkyline> s1 = new ArrayList<TipoSkyline>();
ArrayList<TipoSkyline> s2 = new ArrayList<TipoSkyline>();

m = (i + j - 1)/2;
n = j - i + 1;

if (n == 1) {
s.add(new TipoSkyline(Integer.valueOf(c.get(0).getInicio()), (Integer.valueOf(c.get(0).getAltura()))));
}

else; {
DyV(c, i, m, s1);
DyV(c, m+1, j, s2);
Combinar(s1, s2, s);
}
}

Donde considero que el caso base es cuando solo hay un edificio y lo introduce directamente en la salida.
En otro caso, aplicamos DyV a n/2 del arraylist Ciudad y volvemos aplicar DyV. Para que en la ultima llamada se vaya aplicando recursivamente combinar que se encarga de cuadrar cada uno de los solapamientos al ir avanzando en la pila de llamadas...

Los fallos en tiemp ode ejecución aún no he empezado a mirarlos, por lo que el algoritmo puede que este mal.
Pero no puedo avanzar hasta que no solucione estos problemas en tiempo de ejecución...

Gracias CapacProg por molestarte en responderme. Espero haberte dado la información necesaria...
Gracias de nuevo y Feliz 2012.

[CapacProg]

Código C#:

DyV(c, i, m, s1);
 

De este trozo de código he probado para diferentes valores de i, j y veo que n no converge a 1, da para ciertos valores; pero la convergencia debe ser única como la definición de límite en matemáticas. Motivo por el cuál es una llamada recursiva infinita y el motivo del java.lang.StackOverflowError.

Mientrás que:

Código C#:

DyV(c, m+1, j, s2);
 

si da para cualquier valor una convergencia de n=1.

Revisa entonces la primera llamada recursiva y solucionarás tu problema.

[Kyokatallama]

Buenas tardes,

Siento molestarte de nuevo CapacProg.

No he podido trabajar sobre el aspecto que me dijiste porque estas dos líneas de código:

ArrayList<TipoSkyline> s1 = new ArrayList<TipoSkyline>();
ArrayList<TipoSkyline> s2 = new ArrayList<TipoSkyline>();

Me dan un error de tipo:

Exception in thread "main" java.lang.StackOverflowError

En tiempo de compilación...


No entiendo el problema, pues sólo declaro y creo un objeto de la clase. Pero este fallo sigue sin permitirme avanzar...

Alguno tenéis idea de cual puede ser el problema??

Gracias anticipadas.

[CapacProg]

No creo que ese sea tu problema, la excepción que obtienes es debido a que el programa desbordo la capacidad de memoria en la pila de llamadas, que en tu caso es por llamar infinitas veces a DyV. Comenta las llamadas recursivas una a la vez y te darás cuenta, que en la primera falla y en la segunda no.

[Kyokatallama]

Ya encontré el problema CapacProg.

Se debía a una mala llamada inicial, que sacaba de rango el arraylist y por un ";" perdido que evitaba entrar en una rama de la recursión...

Gracias por las molestias que te has tomado en echarme un cable.

Un saludo y muchas Gracias.

[CapacProg]

Ok, no hay problema.