Ricorsione

[andbin]

Salve a tutti. Chiedo consiglio qui visti i miei continui fallimenti. Dovrei scrivere un metodo ricorsivo, che, a partire da un ArrayList, restituisca una sua copia con gli stessi elementi in ordine opposto. Grazie a chiunque voglia aiutarmi.

Quali sono esattamente i dubbi? Hai già provato a ragionarci un po'? Hai scritto del codice?
Precisa anche se devi fare un metodo "generico" (nel senso dei generics di Java 5, che valga per un ArrayList<QualunqueTipo> ) oppure per un tipo specifico.

P.S: il fatto che il ArrayList in ingresso NON vada toccato, è chiaramente solo una piccola complicazione in più.

[VinSmoke]

Quali sono esattamente i dubbi? Hai gi� provato a ragionarci un po'? Hai scritto del codice?
Precisa anche se devi fare un metodo "generico" (nel senso dei generics di Java 5, che valga per un ArrayList<QualunqueTipo> ) oppure per un tipo specifico.

P.S: il fatto che il ArrayList in ingresso NON vada toccato, � chiaramente solo una piccola complicazione in pi�.

Non e' specificato quale tipo utilizzare. La domanda così come l'ho scritta, mi e' stata posta. Uno dei dubbi che ho riguarda i parametri in input; cioè, se chiede "a partire da un ArrayList...", dovrei immaginare di scrivere:

static ArrayList<?> reverse( ArrayList<?> listIn ){
//....
//....
}

Tuttavia mentre scrivo e riscrivo codice sento la necessità di utilizzare anche un indice (per scandire gli elementi), da prendere in input e da passare nella chiamata ricorsiva. Probabilmente non e' necessario e nemmeno richiesto, ma fino ad ora non sono riuscito a fare altrimenti.

[andbin]

se chiede "a partire da un ArrayList...", dovrei immaginare di scrivere:

static ArrayList<?> reverse( ArrayList<?> listIn ){

Ehm, no. Questo intanto non è un metodo "generico". Hai solo usato dei unbounded wildcard. Che però ti creeranno solo "grane". Grane sia a livello di implementazione (un elemento lo puoi estrarre solo come Object e non puoi inserire nulla in un ArrayList<?> .. a parte un null letterale) e grane nell'uso finale (se gli passi un ArrayList<String> ok ma poi NON puoi assegnare il valore restituito ad una variabile ArrayList<String>).

Meglio un metodo veramente "generico":

public static <T> ArrayList<T> reverse(ArrayList<T> input)

Tuttavia mentre scrivo e riscrivo codice sento la necessità di utilizzare anche un indice (per scandire gli elementi)

Non devi usare alcun indice né "scandire" la lista ... altrimenti stai facendo qualcosa di iterativo, non ricorsivo.

Il concetto è semplice: ricevi una lista, ne fai innanzitutto una copia (vedi costruttore di ArrayList) perché l'input non lo devi toccare (vale per la prima chiamata ma vale allora anche per quelle ricorsive), poi estrai (nel senso di ottenere ma anche proprio togliere) il primo elemento. Quindi chiami ricorsivamente con la lista che rimane. Alla fine aggiungi al fondo l'elemento tolto dall'inizio.
Ogni chiamata ricorsiva farà così. Chiaramente devi studiare la condizione per non procedere nella ricorsione ad un certo punto.

Per altri dubbi, chiedi.

[VinSmoke]

Ehm, no. Questo intanto non è un metodo "generico". Hai solo usato dei unbounded wildcard. Che però ti creeranno solo "grane". Grane sia a livello di implementazione (un elemento lo puoi estrarre solo come Object e non puoi inserire nulla in un ArrayList<?> .. a parte un null letterale) e grane nell'uso finale (se gli passi un ArrayList<String> ok ma poi NON puoi assegnare il valore restituito ad una variabile ArrayList<String>).

Meglio un metodo veramente "generico":

public static <T> ArrayList<T> reverse(ArrayList<T> input)


Non devi usare alcun indice né "scandire" la lista ... altrimenti stai facendo qualcosa di iterativo, non ricorsivo.

Il concetto è semplice: ricevi una lista, ne fai innanzitutto una copia (vedi costruttore di ArrayList) perché l'input non lo devi toccare (vale per la prima chiamata ma vale allora anche per quelle ricorsive), poi estrai (nel senso di ottenere ma anche proprio togliere) il primo elemento. Quindi chiami ricorsivamente con la lista che rimane. Alla fine aggiungi al fondo l'elemento tolto dall'inizio.
Ogni chiamata ricorsiva farà così. Chiaramente devi studiare la condizione per non procedere nella ricorsione ad un certo punto.

Per altri dubbi, chiedi.

Grazie mille per l'aiuto. Questo è quanto sono riuscito a produrre (funzionante) :

static <T> ArrayList<T> reverseList(ArrayList<T> listIn){
T obj = null;
ArrayList<T> copia = listIn;
if(copia.get(0) != listIn.get(listIn.size()-1)){
obj = copia.remove(0);
reverseList(copia).add(obj);
}else{
return copia;
}
return copia;
}

[andbin]

ArrayList<T> copia = listIn;

Mi spiace, questa è solo una copia del riferimento ... NON è una copia dell'oggetto ArrayList.
Se il requisito del metodo è "non modificare il ArrayList ricevuto in ingresso", il tuo codice purtroppo non va bene.

Inoltre
if(copia.get(0) != listIn.get(listIn.size()-1)){

non vuol dire nulla di sensato.