HW8obb dove si puo usare la ricorsione?

Tommaso Sgroi (12990 points)
6 11 91
asked Dec 9, 2019 in HW8 obbligatorio by Tommaso Sgroi (12,990 points)
closed Dec 10, 2019 by Tommaso Sgroi

Il testo dell'homework dice:

NOTA: almeno una delle funzioni realizzate DEVE essere ricorsiva, ad esempio
    potete scandire la matrice iterativamente e le lettere della parola cercata ricorsivamente.

Nulla quindi vieta di  trovare matrice e parole ricorsivamente mentre si cercano le parole all'interno della matrice iterativamente?

664 views
closed with note: Risolti i dubbi

5 Answers

AndreaGasparini (18730 points)
6 12 118
answered Dec 9, 2019 by AndreaGasparini (18,730 points)
edited Dec 9, 2019 by AndreaGasparini
Nulla lo vieta, l'importante è che per ogni input la funzione ricorsiva venga sempre richiamata senza fermarsi al solo caso base. Ovviamente non vale mettere chiamate ricorsive a caso e poi risolvere tutto iterativamente.

Il suggerimento dello scandire la matrice iterativamente e controllare i percorsi delle parole ricorsivamente penso sia stato dato in quanto più "logico" da un punto di vista del concetto di ricorsione. Analizzando un problema simile, una soluzione ricorsiva dovrebbe essere la prima a venirti in mente.
Tommaso Sgroi (12990 points)
6 11 91
commented Dec 9, 2019 by Tommaso Sgroi (12,990 points)
Che sia più logico non c'è dubbio, alla fine il procedimento è per certi versi simile alla ricerca negli alberi binari.
Io infatti ho risolto il problema in maniera ricorsiva per la ricerca nella matrice e ritorna tutti i valori corretti ma dato che sulla VM va in timeout su un test,  volevo provare a risolvere il problema in maniera iterativa e vedere quale dei due fosse più veloce.
edoardottt (8210 points)
1 3 37
answered Dec 9, 2019 by edoardottt (8,210 points)
No. Credo proprio di no. Hai almeno una funzione ricorsiva nel tuo programma.
E
Edward (25950 points)
2 4 172
answered Dec 9, 2019 by Edward (25,950 points)
Teoricamente il testo è abbastanza vago, e se volessi imbrogliare potresti anche fare una funzione ricorsiva che ti calcola il fattoriale di 2 e passare i test (i test della VM ovviamente, poi l'homework verrebbe probabilmente annullato).

Quindi quello che dici tu teoricamente è corretto, io ti consiglio però di fare come dice la traccia, ossia impostare la ricorsione nella ricerca della parola, che per come è impostato l'esercizio ha senso.
Non so se invece ha molto senso trovare matrice e parole ricorsivamente... (se intendi all'interno del file)
Tommaso Sgroi (12990 points)
6 11 91
commented Dec 9, 2019 by Tommaso Sgroi (12,990 points)
Io in realtà avrei già risolto l'homework usando la ricorsione per "rovistare" nella matrice e trovare il percorso ritornandolo esatto... Però dato che fallisce un test per il timeout volevo sapere se era possibile risolverlo in maniera iterativa per vedere se le tempistiche cambiavano.
La mia intenzione non era assolutamente quella di "imbrogliare", proprio per questo volevo sapere se fosse lecito questo approccio.
E
Edward (25950 points)
2 4 172
commented Dec 9, 2019 by Edward (25,950 points)
Provare puoi provare... probabilmente ti fa guadagnare qualcosa perchè risparmi il tempo delle varie chiamate alla funzione, ma dubito tu riesca a superarlo semplicemente cambiando da ricorsiva ad iterativa. Se ci riuscissi, probabilmente è perchè hai migliorato l'algoritmo, e questa miglioria dovresti riuscire ad effettuarla anche nella ricorsione.
plm (18850 points)
7 15 118
answered Dec 9, 2019 by plm (18,850 points)

L'esercizio richiede di utilizzare ALMENO una funzione ricorsiva. Ricordati sempre che per fare in modo di far riconoscere la tua funzione ricorsiva devi rispettare questi step (cito Edward):

 Solo che se la funzione ricorsiva è quella innestata, non viene rilevata, quindi almeno una devi definirla al livello più esterno.

Tommaso Sgroi (12990 points)
6 11 91
commented Dec 9, 2019 by Tommaso Sgroi (12,990 points)
Che si intende per "livello più esterno"?
E
Edward (25950 points)
2 4 172
commented Dec 9, 2019 by Edward (25,950 points)
Lo stesso livello nella quale è definita la funzione es1()

Ossia:
def es1():
    blabla

def funzRicorsiva():
    blabla

va bene

invece

def es1():
    blabla
    def funzRicorsiva():
        blabla

non va bene.

In alternativa la funzione ricorsiva può essere il metodo di una classe.
Tommaso Sgroi (12990 points)
6 11 91
commented Dec 9, 2019 by Tommaso Sgroi (12,990 points)
Grazie mille!
Andrea Sanchietti (3100 points)
4 7 40
answered Dec 9, 2019 by Andrea Sanchietti (3,100 points)
Si, puoi farlo ma ti consiglio di provare a usare la ricorsione sulla matrice comunque.

io per esempio avevo avuto come idea quella di crearmi degli alberi ennesimali in modo ricorsivo per poi cercarli nella matrice ma purtroppo mi sono bloccato alla reazione di essi :(