Che vantaggio c'è nell'usare la ricerca binaria ricorsiva sulla ricerca binaria iterativa o viceversa?

Naviga le tue risposte
5

In un recente incarico per la mia classe di programmazione 2 abbiamo testato l'efficienza delle ricerche popolando un ArrayList java con 13.040 stringhe. La ricerca sequenziale era ovviamente più lenta delle ricerche binarie a causa della differenza di complessità e della quantità di volte in cui il codice deve effettivamente scorrere il codice.

La ricerca binaria iterativa e la ricerca binaria ricorsiva, tuttavia, avevano la stessa quantità di confronti. Ad esempio: 

sequentialSearch(): 'some_word' found in ArrayList at index 13,020 - comparisons: 13,021

I confronti sono il numero di volte in cui il computer ha effettivamente verificato se "some_word" dell'utente era uguale a un valore ArrayList. 

iterativeBinarySearch(): 'some_word' found in ArrayList at index 13,020 - comparisons: 14
recursiveBinarySearch(): 'some_word' found in ArrayList at index 13,020 - comparisons: 14

Quindi, se i confronti tra iterativo e ricorsivo sono gli stessi, in quali situazioni sceglieresti l'uno rispetto all'altro? È semplicemente un gusto personale o esiste un ragionamento specifico per l'utilizzo di uno specifico?

    
posta Jaken Herman 18.02.2015 - 21:41
fonte

2 risposte

8

Se il tuo processore di lingua (compilatore o interprete) implementa correttamente l'ottimizzazione della ricorsione di coda, allora non ci sarà alcuna differenza tra una ricerca binaria ricorsiva codificata correttamente e una ricerca binaria iterativa. Il processore di lingua trasformerà le chiamate ricorsive in loop semplici.

A quel punto, la scelta della formulazione ricorsiva rispetto a quella iterativa è praticamente una questione di preferenza personale e locale. Alcune persone trovano il codice ricorsivo più facile da capire. Alcune persone sono spaventate a morte dalla ricorsione, o non la capiscono, o non hanno idea di ottimizzazione della ricorsione di coda, e vogliono codice esplicitamente iterativo ovunque.

    
risposta data 18.02.2015 - 22:35
fonte
2

Dopo ulteriori ricerche, ho creato alcuni pro / contro su ciascun algoritmo. È più facile visualizzare in una tabella, ma al momento sembra non supportato da markdown. Tuttavia, ho separato questi pro / contro in 6 categorie (struttura, controllo, condizione, aggiornamento, velocità e spazio).

A seconda del progetto a portata di mano questo dovrebbe essere in grado di determinare il miglior algoritmo da praticare.

iterativo

Struttura - Ripetizione
Controllo - Uso esplicito del ciclo
Condizione - Condizione di ingresso
Aggiornamento - È controllato dal contatore e continua ad aggiornare un contatore
Velocità - Di solito viene eseguito più velocemente rispetto a uno spazio ricorsivo Spazio - Di solito occupa meno spazio che ricorsivo.

ricorsivo

Struttura - Selezione
Controllo - Chiamata ricorsiva (vale a dire caso ricorsivo). I dati diventano più piccoli ogni volta che viene chiamato.
Condizione - Condizioni di uscita (vale a dire caso base)
Aggiornamento - Si avvicina gradualmente al caso base. Continua a produrre versioni più piccole ad ogni chiamata.
Velocità - Di solito è più lento di iterativo
Spazio - Di solito richiede più spazio di iterativo, chiamato "call" impili".

risposta data 19.02.2015 - 02:35
fonte

Leggi altre domande sui tag

Strategia per la correzione di avvisi firmati / non firmati Esiste un vantaggio per il codice di test unitario il cui unico scopo è generare codice non leggibile da un utente in un'altra lingua?