Newsgroup: it.comp.java
Titolo: Test d'esame

Salve, in un test d'esame ho trovato questa domanda:
Quale tra le seguenti affermazioni è corretta?
1. Gli algoritmi ricorsivi sono più potenti degli algoritmi iterativi.
2. Gli algoritmi ricorsivi sono meno potenti degli algoritmi iterativi.
3. Gli algoritmi ricorsivi hanno la stessa potenza degli algoritmi 
iterativi.
Voi cosa avreste risposto? Cosa significa potenza?
Grazie mille e ciao a tutti.
Luca

 Luca
io avrei risposto alla 1.
forse per potenza intendono che fai le stesse cose con meno codice.
Davide

> > Voi cosa avreste risposto? Cosa significa potenza?
Con potenza si dovrebbe intendere potere espressivo, cioé quanto puoi fare
avendo o non avendo un costrutto.
Allora la risposta corretta è la 3, perché si può sempre emulare la
ricorsione con l'iterazione e una struttura dati tipo stack.
Ale

 ha scritto nel messaggio
news:br04g8$26qvst$1...@ID-180291.news.uni-berlin.de...

Esatto.
Poi è vero che esistono situazioni in cui è inutile ricorrere ad algoritmi
non ricorsivi, in presenza di problemi in cui la soluzione ricorsiva è
immediata.
Scorpio.

 Con potenza si dovrebbe intendere potere espressivo,
        se intendi  'potenza' come 'potere espressivo',
        dovresti  rispondere 1, secondo me.
       ciao.


        ciao.
No, un linguaggio con l'iterazione e' turing-completo, ed un linguaggio 
con la ricorsione pure. Quindi hanno lo stesso potere espressivo, punto. 
Questa e' teoria di base dell'informatica.
-- 
/**
  * Mattia Belletti - Undergraduate student @ 
cs.unibo.it
  * ICQ: 33292311   - email: 
mbel...@cs.unibo.it
  * IRC: BluShine   - site(s): 
http://cs.unibo.it/~mbellett
  * Linux registered user 299762 @ Linux registered machine 213003
  */


Esatto,
l'avete detto tutti prima, te ne accorgi perchè puoi usare indifferentemente
o l'uno o l'altro costrutto.
Sarebbe stato diverso se esistevano delle situazioni risolvibili sono con
ricorsione o sono con iterazione.
Poi che la ricorsione sia enormemente più affascinante è una questione di
gusti personali, tutto qui.
/* Delvy */

 ha scritto nel messaggio
news:br04g8$26qvst$1...@ID-180291.news.uni-berlin.de...

ESATTO !!! :-)

        ciao.
Errato, tutti i problemi risolvibili con un algo iterativo possono essere
risolti con un algo ricorsivo e viceveresa.
Altra cosa è poi la complessità computazionale che cmq non ha nulla a che
vedere con il numero di righe di codice.
Ciao

 Ale
-- 
questo articolo e` stato inviato via web dal servizio gratuito 
http://www.newsland.it/news
 segnala gli abusi ad 
ab...@newsland.it

 Questa e' teoria di base dell'informatica.
 OK.
Pero':
 su alcuni testi e dispense, nei capitoli relativi alle funzioni ricorsive,
 viene sottolineata la 'potenza della ricorsione',
es: " Le funzioni iterative sono potenti, largamente applicabili, spesso
efficienti ma possono risultare artificiose, poco leggibili e quindi
difficili da comprendere. "
Se non si riferiscono alla potenza espressiva a che tipo di potenza  si
riferiscono e,
inoltre, potenti rispetto a chi?
Ciao.

 ha scritto nel messaggio
news:6kKAb.62259$AX1.2...@news1.tin.it...

secondo me per potenza si voleva intendere efficienza, quindi minor
quantità di tempo impegata nel caso pessimo per fornire un output corretto.
seguendo tale considerazione io avrei risposto 1

 ha scritto nel messaggio
news:br1loq$5op$1...@le1.cs.unibo.it...

turing fu arrestato per omosessualità, così tanto per essere completi
nell'informazione.

 nell'informazione.
Uhm... si', e' vero. Argomento interessante, e da ricordare, non fosse 
altro per quanto riguarda l'infondatezza di qualunque accusa verso 
l'omosessualita', ma... cosa c'entra? ^_^


 Ciao.
Ovviamente ci puo' essere un problema di terminologia. Il punto e' che, 
quando in informatica si parla di "potenza", la scelta di default e' 
"potenza espressiva". Magari messo in un altro contesto puo' avere 
significati diversi, ma senza di esso, e' questo il senso che si da.
Direi che tuttavia basta chiedere al prof in questione quale significato 
voleva dare alla parola "potenza", come stanno le cose lo abbiamo 
chiarito :)


 seguendo tale considerazione io avrei risposto 1
Vedi il resto del thread, e la mia risposta ad oop a riguardo.


 difficili da comprendere. "
Non lo so, a naso direi che significa che in genere le funzioni ricorsive
richiedono meno codice, sono più "eleganti".
Ma non c'entra niente con potere espressivo e calcolabilità.
Tutte e sole (pare che sia così ma non è ancora stato dimostrato) le
funzioni calcolbili sono ricorsive.
Quindi di ogni funzione iterativa si puo' dare una forma ricorsiva.
L'informatica teorica è bellissima
Ciao
Matteo
-- 
chi sono e soprattutto chi non sono:
http://www.ilnomedeldominio.it
un programma per studenti universitari:
http://inutility.ilnomedeldominio.it/imsv/

 Rispetto ad una macchina di Touring:
E Turing si rivolta nella tomba... ;)))))


 E Turing si rivolta nella tomba... ;)))))
:-))))  Cosa vuoi farci...


 seguendo tale considerazione io avrei risposto 1
Beh, non ho avuto tempo di dirvi che io la risposta corretta ce la ho 
:-). Cmq io ho ragionato come te, ma ho risposto 2 (non era l'esame, ma 
solo esercizi). Ho studiato che gli algoritmi iterativi sono sempre più 
veloci degli algoritmi ricorsivi, quindi avrei risposto 2.
In realtà ho dovuta fare una interpretazione del termine potenza, che 
non conoscevo perchè non spiegato. La risposta corretta era la terza, 
quindi aveva ragione Alessandro, almeno secondo il mio prof. Grazie 
mille a tutti per la definizione di potenza, almento ora sono preparato.
Luca

 mille a tutti per la definizione di potenza, almento ora sono preparato.
cmq direi che domande sul testo (se non capisci la domanda, non puoi certo
chiedergli la risposta ;) si possono sempre fare...
Non essere timido ed in casi come questo alzati e vai a chiedere :)


 Non essere timido ed in casi come questo alzati e vai a chiedere :)
Si, ma preferisco non dover dipendere da altri.
Grazie mille a tutti.
Luca

 iterativi.
Ora faccio impazzire tutto il NG.
Per quanto ne so io un algoritmo (in particolare gli NP-Hard) se e'
risolvibile, lo e' sicuramente con il metodo iterativo.
Non tutti gli algoritmi, infatti, sono risolvibili con il metodo ricorsivo.
La potenza di un algoritmo ricorsivo sta nella sua facile implementazione e
facile leggibilita', proprieta' non sempre applicabili ad un algoritmo
iterativo.
In conclusione la domanda e' mal posta!
Se non si da una definizione di "potenza di algoritmo" NON si puo' dare una
risposta.
Se e' un test di esame, dipende, quindi, da come il professore ha definito
la potenza di un algoritmo.
IMHO con potenza si intende "cosa" un algoritmo puo' fare. In questo caso
la risposta sarebbe la 2.
Se si intende la potenza con leggibilita' e implementazione allora la
risposta e' la 1.
In ogni caso, IMHO, la 3 non e' da prendere in considerazione.
Scannatemi pure! :D
-- 
Marco "Duff" Palermo
http://www.marcoduff.com/

 Non tutti gli algoritmi, infatti, sono risolvibili con il metodo ricorsivo.
Beh, quest'ultima frase e' falsa - se fosse vera, le tue conclusioni 
sarebbero corretta :)
Ma cmq, accidenti, questo e' un ng di Java, non sarebbe il caso di 
spostarsi du it.scienze.informatica ? :P


 spostarsi du it.scienze.informatica ? :P
Hai ragione, ma ogni tanto un poco di ragionamenti filosofici ci stanno
dentro! :D
E poi visto quante persone sono state attirate dal thread!!!


 3. Torna al punto 1
Versione ricorsiva:
function ascolta() {
   <attendi una connessione>
   <dai il benvenuto al client>
   ascolta();
}
Perché nessun programmatore sano di mente farebbe questo? Perché ad un certo
punto per via dell'accumularsi dei record di attivazione finirebbe la
memoria...
E allora?
Questo è un limite fisico delle nostre macchine non della ricorsione.
Ad oggi si ritiene che le funzioni calcolabili siano tutte e sole quelle
calcolabili da una macchina di Turing. Esiste una corrispondenza biunivoca
tra macchine di Turing e funzioni calcolabili.
Quindi: tutte le funzioni calcolabili secondo Turing sono ricorsive.
Cioé tutte le funzioni calcolbili (finché qualcuno non dimostra il
contrario) sono ricorsive.
Ficcatelo in testa ;) Non c'é niente di piu' "potente" della ricorsione.
E' un limite teorico, nessun Pentium 4 dei miei stivali puo' fare meglio ;))
E non dimentichiamo una cosa... una macchina di Turing opera su un nastro
infinito, o al piu' semi-infinito, cioé senza limiti di memoria... il che
chiarisce la questione di prima :)


 chiarisce la questione di prima :)
Ok, ok...
Abbiamo qualche problema con la definizione.
Se si definisce con "Funzione Ricorsiva":
1. "Una funzione che semplicemente richiama se stessa"
hai ragione tu (voi).
Ma se si definisce (come ho *sempre* visto ovunque):
2. "Una funzione che richiama se stessa. La funzione deve ammettere una
condizione di uscita."
la cosa cambia...
Ora, sono d'accordo che qui la mia pignoleria sta arrivando alle stelle e
che l'eventuale differenza tra ricorsione/iterazione si riduce a poche
applicazioni particolari, ma per la prima volta sto per risolvere uno dei
miei grossi dubbi sulla programmazione... Per questo vi ringrazio!


 del mio algoritmo)!
E se aggiungessimo un bel
if(1==0)
  return ?
La condizione ci sarebbe, ma non sarebbe mai verificata... fatta salva la
definizione, il succo non cambia.
Scorpio (che si scusa con Turing per averne storpiato il nome...)

 la cosa cambia...
Nessuna della due è la definizione di funzione ricorsiva.
La definizione è matematica e si basa su certe funzioni elementari dai
naturali ai naturali e sulla loro composizione secondo operatori che ora
non ricordo ;)
Quindi ben piu' complicata di quella che dici tu. D'altra parte è su questa
definizione che si basa la calcolabilità.
Mi sembra inutile andare oltre.
Ma ti consiglio di non essere troppo convinto di quella tua teoria, e se
studi informatica ne riparliamo quando hai fatto informatica teorica ;))





 definizione, il succo non cambia.
Non credo che vale! In questo modo bari! :p
Se metti un return cambi l'algoritmo da me dato, ne hai conferma anche
guardando il tuo punto interrogativo, non sai cosa metterci perche'
l'algoritmo non prevede di metterci nulla!


 studi informatica ne riparliamo quando hai fatto informatica teorica ;))
No, non sono molto convinto della mia teoria, ed e' per questo motivo che
voglio piu' chiarezza...
Se ti trovi sotto mano la "vera" definizione di Funzione Ricorsiva,
potresti postarla? (Anche in privato se vuoi chiudere il thread).
A me la definizione di funzione ricorsiva mi e' stata sempre data in questo
modo, e ne ho conferma anche qguardando i libri che ho a disposizione...
Grazie.


 l'algoritmo non prevede di metterci nulla!
Il "?" era riferito alla proposta di usare un if(1==0) etc, non al return.
Potremmo restituire un valore booleano od un intero, non cambierebbe
nulla...
So che è un modo per barare, però ai fini pratici non cambierebbe molto, o
no ?
Scorpio.

 no ?
No, non cambia proprio nulla sotto un punto di vista pratico...
Ma il punto e' che stiamo esaminando la questione sotto un punto *teorico*,
o meglio *filosofico*, quindi non si puo' barare! ;D
