gestione funzione ricorsiva

[Epris]

ciao a tutti,

avevo implementato una funziona ricorsiva il cui scopo è quello di individuare tutti i percorsi su un grafo.

Per sommi capi il codice richiama una funziona calcolaCammini(Percorso Soluzione, int posizione).
Soluzione è un oggetto che al suo interno istanzia un ArrayList dei nodi del grafo. Posizione invece indica la i-esima posizione nel cammino per la quale si sta scegliendo il nodo.

  private void calcolaCammini(Percorso soluzione, int posizione) {


    if(in soluzione(posizione) c'è l'ultimo nodo del grafo)
    {
      cammini.add((Percorso)soluzione.clone());
    }
    else {
      posizione+=1;
      nodiCandidati= insieme dei possibili nodi da inserire in soluzione(posizione);

        Iterator it = nodiCandidati.iterator();

        while (it.hasNext()) {

          Vertice elemento = (Vertice)it.next();

          Percorso copiaPercorso=(Percorso)soluzione.clone();
          (copiaPercorso).aggiornaPath(elemento);


          calcolaCammini(copiaPercorso,posizione);

        }
      }

    }

Ho utilizzato il metodo clone per effettuare una copia di "soluzione" che passo alla funzione ricorsiva altrimeti anche se l'avessi aggiunta a cammini me la cambiava quando iniziava a risalire lungo la funzione ricorsiva. Vi faccio un esempio per farvi capire cosa succedeva non usando un clone.
mettiamo che io aggiunga a cammini la stringa "ciao" (dove 'c' è un nodo, 'i' è il successivo e cosi via).
Ora la funzione ricorsiva inizia a risalire.. e trova una nuova soluzione "ciaa" e l'aggiunge in cammini. In cammini avrò ora "ciaa" e "ciaa".

Il problema è che visto che alcune volte il grafo è enorme.. supero la dimensione dell'heap.
Volevo sapere.. c'è un modo per evitare questi clone?

[Ascia75]

sicuramente fai una copia doppia e quindi puoi ridurre il carico dell'heap di metà.

infatti:

mettiamo che entri nel metodo ricorsivo la prima volta, entri nell'else, fai la copia e richiami il metodo ricorsivo sulla copia. mettiamo che ora invece entri nell'if, fai una copia su qualcosa che è già una copia.


Se poi l'algoritmo è giusto o si può migliorare onestamente non lo so, sono un po' arrugginito sui grafi..