Do you need any help?

Notice Board

Per partecipare al corso di Fondamenti di programmazione 2021-22 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 2021-22 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.

VIDEOLEZIONI DEL CORSO DI FONDAMENTI DI PROGRAMMAZIONE AA20-21

PROGRAMMING COURSE VIDEOCONFERENCES AY20-21

Es1 Test2 Ho una funzione ricorsiva ma non viene usata e quindi non viene trovata

VincenzoImperati (6250 points)
1 11 54
asked Dec 24, 2018 in Es1 by VincenzoImperati (6,250 points)
Come detto nel titolo il mio algoritmo ha una funzione ricorsiva e viene richiamata in tutti e sette i test e di conseguenza va in ricorsione, in tutti i test tranne nel numero 2. Questo perché il test 2 presenta solo alberi fatti da radice-foglia. Questa situazione per me è il caso base della ricorsione (anche perché da come ci vengono forniti i dati non è possibile avere un arco dove è presente solo il padre o solo il figlio) e quindi gli alberi vanno nella funzione ma escono subito per il caso base non avviando una ricorsione. Nella consegna c'è scritto che bisogna creare una funzione ricorsiva, ed è quello che faccio ma non c'è scritto di preoccuparsi che tutti i test vadano obbligatoriamente in ricorsione. Detto questo devo pensare ad un nuovo codice o c'è qualche altra soluzione? Ma comunque ogni funzione ricorsiva ha un caso base che, se qualcosa entra nella funzione, ed è già il caso base allora non va in ricorsione. Quindi il problema si potrebbe sempre presentare
243 views

2 Answers

_andrea_ (45670 points)
2 40 297
answered Dec 24, 2018 by _andrea_ (45,670 points)
Come la calcoli l'altezza degli alberi? In teoria quella dovrebbe essere ricorsiva
VincenzoImperati (6250 points)
1 11 54
commented Dec 24, 2018 by VincenzoImperati (6,250 points)
Se ho solo alberi: radice-foglia l'altezza è 2 di base quindi non ho bisogno di ricorsione
_andrea_ (45670 points)
2 40 297
commented Dec 24, 2018 by _andrea_ (45,670 points)
Eh ma come fai a sapere che hai solo alberi così? Hai una funzione che si chiama altezza? Come funziona?
VincenzoImperati (6250 points)
1 11 54
commented Dec 24, 2018 by VincenzoImperati (6,250 points)
Mando nella funzione ricorsiva un albero alla volta. Partendo dalla radice controllo i suoi figli, se nessuno di questi ha figli allora l'albero ha altezza 2 ed esco dalla funzione direttamente dal caso base senza fare una ricorsione. Il test due percorre solo questa parte della mia funzione ricorsiva quindi mi dice che non è presente una funzione ricorsiva. Ho solo alberi di altezza due perché il test due solo quelli mi da
_andrea_ (45670 points)
2 40 297
commented Dec 24, 2018 by _andrea_ (45,670 points)
E allora cambia quel caso base. Invece che un albero e una foglia metti che il caso base è una foglia che torna 1
andrea.sterbini (172780 points)
513 935 1789
answered Dec 24, 2018 by andrea.sterbini (172,780 points)
Ora che ci penso c'è un caso in cui la foresta è formata da solo archi separati ed in cui la chiamata ricorsiva, se esce immediatamente tramite caso base, non viene individuata.

Cambia leggermente la tua funzione in modo da contare i nodi e fare una chiamata ricorsiva anche per singoli archi.
VincenzoImperati (6250 points)
1 11 54
commented Dec 24, 2018 by VincenzoImperati (6,250 points)
ho aggiornato il codice. Prima avevo un for che mi mandava ogni albero nella funzione ricorsiva, adesso ho trasformato quel for in una f ricorsiva così che se c'è almeno un albero nella foresta avviene la ricorsione, ma così facendo non passo il test numero 6 (quest'ultimo ha 4911 alberi alti da 2 a 5 da ciò che sono riuscito a vedere) perchè da come ho interpretato il messaggio di errore(maximum recursion depth exceeded while calling a Python object) supero il limite di ricorsioni. Non so dove tentare altre ricorsioni (banali) affinchè anche il test 2 vada in ricorsione (perchè questo era il mio problema iniziale) senza che siano troppe da superare il limite di ricorsioni
andrea.sterbini (172780 points)
513 935 1789
commented Dec 24, 2018 by andrea.sterbini (172,780 points)
Non serve che inventi ricorsioni inutili.

Fai un caso ricorsivo per la misura dell'altezza leggermente diverso in modo da contare 0 per i singoli nodi e 1+ per ogni figlio e vedrai che anche la foresta di singoli archi andrà bene.