[Java] Ricerca binaria ricorsiva

[stefano86]

Ciao a tutti, sto studiando algoritmi e precisamente la ricerca binaria iterativa e ricorsiva in Java.
Ad un certo punto le slide dicono che l'alg. di ricerca binaria ricorsiva è meno efficiente di quello iterativo, specialmente in termini di spazio.
Qualcuno potrebbe spiegarmi il perchè? Io erroneamente pensavo fosse più veloce la procedura ricorsiva che quella iterativa..

Di seguito ci sono le due versioni.

Iterativa:

Codice:

public class IntArrayOrdinato {
…
public static int ricercaBinaria(int x) {
   int inf = 0;
   int sup = numElementi - 1;
   if(sup == -1 || x < a[0])
      return -1;
   if(x > elementi[sup])
      return –(numElementi + 1); //oppure – numElementi - 1
   //IC(Invar. di ciclo): se x in a, allora x in a[inf…sup]
   while(inf <= sup) {
      int i = (inf + sup) >>> 1;
      if(x < elementi[i])
         sup = i - 1;
      else if(x > elementi[i])
         inf = i + 1;
      else return i;
   }
   return –(inf + 1); //posizione di inserimento
}
…
}



Ricorsiva:

Codice:

public static int ricBin(int x, int[] a) {
   return ricBin(x, a, 0, a.length - 1);
}

static int ricBin(int x, int[] a, int inf, int sup) {
   if(inf > sup)
      return -1;
   else {
      int i = (inf + sup) >>> 1;
      if(x < a[i])
         return ricBin(x, a, inf, i-1);
      else if(x > a[i])
         return ricBin(x, a, i+1, sup);
      else
         return i;
   }
}



Grazie

[Giux]

Perchè la ricorsione fa uso del meccanismo dello stack e dei record di attivazione, infatti avrai sicuramente notato che in una funzione(ricorsiva) in Java piuttosto che in C\C++, ecc.., c'è sempre almeno una chiamata alla funzione stessa è questo fa si che ad ogni chiamata corrisponda per l'appunto, una nuova occupazione di memoria sullo stack... e quindi un maggiore spreco di memoria... la versione iterativa generalmente è più efficiente della corrispettiva versione ricorsiva, ma in molte situazioni la versione ricorsiva è più facile da realizzare....

[Giova411]

Bella domanda. Io direi che le slide non sono correttissime
E poi dipende molto se sono ordinati o meno... Se non sono ordinati devo vedere tutti gli elementi uno ad uno
La soluzione più intuitiva è quella di fare un ciclo e scorrere tutti gli elementi quindi $O(n)$: è una soluzione "naif" che non utilizza memoria aggiuntva.
La versione "divide et impera" di binarySearch è $O(log n)$ perché dividi l'input ogni chiamata diviso 2, ma paghi in termini si spazio allocato: il famoso stack che crea la ricorsione.

[onlyReferee]

Ciao stefano86
Come hanno giustamente spiegato i colleghi purtroppo molte funzioni ricorsive seppur sembrino migliori poiché il codice è più compatto rispetto alla versione iterativa offrono spesso una peggiore complessità a livello spaziale. Questo fatto non è molto evidente di per sé poiché l'occupazione della memoria stack con le funzioni ricorsive la si può vedere bene solo mediante le ricorrenze (vedasi teorema dell'esperto) prima di rendersi conto del costo effettivo.

[stefano86]

Grazie a tutti, ho capito però ho una curiosità: è così "grave" occupare tanta memoria? Forse è una domanda stupida..

[Giova411]

Dipende quando.. Al'inizio, quasi ogni corso di Algo1, esamina con più enfasi la complessità temporale... Poi, per magia, scopri che anche quella spaziale ha la sua importanza quando iniziano a discutere di alberi, grafi etc... Nella ricerca binaria però fai conto che hai qualcosa (dato) di ordinato quindi, secondo me, la ricorsione è un'ottima scelta. Però rettifico quanto ho detto prima le slide del Prof non sono sbagliate

[onlyReferee]

Diciamo che è "grave" occupare tanta memoria primo per il fatto che la stessa è una quantità finita e secondo nella misura in cui ci si rende conto che con altri accorgimenti si potrebbe fare molto meglio.