Please ignore secret bonuses. Secret tests do NOT award bonus. Max hw grade is 30+2 bonus efficiency

Do you need help?

Notice Board

Per partecipare al corso di Fondamenti di programmazione 2023-24 loggatevi e attivatelo nella vostra pagina dei corsi preferiti. A quel punto il corso appare nel menù personale cliccando sul proprio avatar. Per i materiali degli anni precedenti seguite lo stesso metodo.

To join the Programming/Lab 2023-24 course, log-on and select it on the my courses page. It will appear on the personal menu of your avatar. For earlier years use the same method.

Ricorsione per l'esercizio 3. E' fattibile?

Gianluigi (1420 points)
10 17 30
in Es3 by (1.4k points)
closed by
Ciao a tutti,

ho provato a risolvere l'esercizio 3 usando la ricorsione per prendere l'insieme di tutti i pixel connessi al pixel di partenza.
Fino all'ottavo test tutto bene. Per gli ultimi quattro, invece, raggiungo il numero massimo di ricorsioni (che ho settato a 4500). Aumentando il numero di ricorsioni massime python smette di funzionare.

A questo punto, vorrei sapere se qualcun altro ha scelto di utilizzare la ricorsione e se è riuscito a superare gli ultimi test, oppure mi conviene abbandonare la strada della ricorsione. A questo proposito, magari, vorrei anche un parere del prof.

Ed eventualmente, come conviene sostituire la ricorsione? Con While e for annidati?
599 views
closed with the note: answered

4 Answers

Best answer
edoardo (7090 points)
19 52 67
by (7.1k points)
selected by

Personalmente credo che il 3 non sia fattibile (a prima vista) con la ricorsione. Magari c'è qualcuno che c'è riuscito, ma sicuramente è facilissimo incorrere nel max depth recursion o avere problemi con python.

Per cambiare la tua funzione da ricorsiva a iterativa ti conviene utilizzare, come dici tu, cicli while e/o cicli for annidati. Ti lascio questa specie di "tutorial" che avevo letto tempo fa e avevo trovato molto utile.

Gianluigi (1420 points)
10 17 30
by (1.4k points)
Grazie mille per il tutorial! Mi è stato utile nella conversione della funzione da ricorsiva a iterativa
Luca T. (5410 points)
3 20 38
by (5.4k points)
Credo che la ricorsione sia da evitare in questo homework, scorrere tutti i pixel di un'immagine richiede tanti passaggi. Tra le ultime immagini ci sono anche delle immagini 400x400 pixel, ovvero 160000 pixel e anche se non ci fosse il problema del limite di ricorsioni, ricorda che le funzioni ricorsive sono più lente e quindi perderesti sicuramente anche l'accesso a eventuali punti bonus per la velocità del programma, se riesci a superare il time out.
ClaudioDiCocco (710 points)
7 17 24
by (710 points)
Ciao,

inizialmente ho provato anch'io la strada bella ricorsione ma dato il troppo elevato numero di richiami troppo elevato (considera che gia' nel primo esercizio il quadrato su cui lavori e' di dimensioni 50*50 percio' 2'500 cicli circa.) ho optato per "trasformare" le ricorsioni in cicli (for o while che siano) e devo dire che la cosa funziona. devo pero' tuttora ridurre i tempi che dal 8 in poi cominciano ad essere enormi.

Spero di esser stato utile
andrea.sterbini (207920 points)
749 1267 2373
by (208k points)

L'immagine a spirale è fatta apposta per mettere in imbarazzo algoritmi ricorsivi devil