[JAVA] Ricorsione

[marco_tacconi]

Salve a tutti, non sono riuscito a capire se questo thread rispetta il regolamento oppure no, ad ogni modo chiedo scusa nel caso fosse così.
Non riesco assolutamente ad afferrare il concetto della ricorsione, ad esempio se ho questo frammento di codice :

public static boolean occorreRic (int[] a, int n){
  return occorreRic(a,n,o);
}

public static boolean occorreRic (int[] a, int n, int i){
  if (i == a.length)
    return false;
  if (a[i] == n)
    return true;
  return occorreRic(a,n,i+1);
}

Allora, ho capito che la ricorsione consiste in un metodo che richiama se stesso, e nel caso di ricerca in array devo fare la ricorsione annidata, quindi devo creare un metodo ricorsivo di controllo e un metodo di ricerca.
Ma esattamente come lavora la ricorsione?

Grazie

[valia]

quando fai la ricorsione chiami te stesso, in genere non un metodo overloaded.

Devi fissare due cose: punto di stop e punto di chiamata a te stesso.
Prova a pensare al calcolo di un fattoriale: hai un valore intero, (es. 4) , 4! equivale a

4*3*2*1

ricordando che 0! = 1.

un metodo ricorsivo potrebbe essere

	public static int ric(int val ){
		  if (val==0) return 1;
		  else return val * ric(val-1);
	}

poi vedi tu cosa devi fare

[Pastore12]

Guardando i tuoi metodi, direi che il primo, occorreRic (int[] , int ), non è ricorsivo, ma è il metodo che va chiamato per far iniziare la ricorsione.

Il secondo metodo occorreRic (int[], int, int) è il metodo ricorsivo vero e proprio, ma credo che in genere vada definito "private" e non "public", perché dovrebbe essere invocato solo tramite il precedente.

Una osservazione possibile è che l'array A contiene n se la prima cella di A è n oppure il resto di A (tutte le celle di A tranne la prima) contiene n.

Ora però anche il resto di A, chiamiamolo A' è un array, per cui la soluzione è come sopra: A' contiene n se la prima cella di A' è n oppure il resto di A' contiene n.

La tecnica è la stessa, ma viene applicata su array più piccolo.

Appena trovi n come primo elemento, cominci a "risalire" la ricorsione perché puoi già dire che A contiene n.

Se non trovi nulla in nessun sottoarray, restituisci false